Largest Rectangle in Histogram
- 3 min read
- Stacks
- LC-Hard
3 years ago
m
Solution
- Monotonic Stack (Increasing)
- Two conditions:
-
- When a subsequent height increases, add the current height to the stack, and keep the previous height in the stack (because it can be extended further)
-
- When a subsequent height decreases, it means the previous height cannot be extended further, so we immediately pop the previous height from the stack, calculate the area it could've occupied, and carry on. One important thing here is that while we're popping the stack, we need to update the
startindex of the height we're about to insert, since if the height is decreasing, it still means that the new lower height can extend backwards. When we updatedstartto be the height of the height we just popped, it means we're accounting for the fact that the current rectangle can extend backwards.
- Kinda think of it like this, whenever we see a new height that violates our monotonic stack property, we are now dealing with all the rectangles that came before it, that were in increasing order
- These rectangles that were in increasing order were ones that could be extended forward, and therefore, when updating the max area, we will need to get the minimum height of the rectangles, and this obviously would be the currently rectangle we're popping because if it was in the stack, it means the rectangles that came after were either the same height or in increasing order
- When a subsequent height decreases, it means the previous height cannot be extended further, so we immediately pop the previous height from the stack, calculate the area it could've occupied, and carry on. One important thing here is that while we're popping the stack, we need to update the
-
- Only after doing all this do we append the current height to the stack.
- Update
max_areaeach time in the loop. - At the end, the elements in the stack are all elements that extended to the end of the
heightsarray, so account for those as well by updatingmax_areaif applicable. Remember, they end at the end of theheightsarray but they might not have necessarily started there. That's why their width is calculated withlen(heights) - i. - If you're still confused, watch the NeetCode video. It'll make it clear.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def largestRectangleArea(self, heights: List[int]) -> int:
max_area = 0
stack = [] # (index, height)
for index, height in enumerate(heights):
start = index
while stack and stack[-1][1] > height:
i, h = stack.pop()
start = i
max_area = max(max_area, h * (index - i))
stack.append((start, height))
for i, h in stack:
max_area = max(max_area, h * (len(heights) - i))
return max_area