largest_rectangle_in_histogram
1# @leet start 2class Solution: 3 def largestRectangleArea(self, heights: list[int]) -> int: 4 """ 5 This question asks us to find the largest rectangle in a set of 6 heights. 7 8 We can do this in $O(n)$ time with $O(n)$ space, using a monotonic 9 stack. 10 11 We only want to keep the largest item we've seen so far on the stack, so 12 if we see an item that's larger than the top of the stack, we pop it 13 and immediately process it to see if it would create a larger rectangle 14 than currently exists. 15 After we're done processing those items, we add the current height + index to 16 the monotonic stack. 17 18 We also want to handle the edge case where either the start or end of heights 19 could contain the largest rectangle, so we add a [0] at both ends. 20 """ 21 22 max_area = 0 23 stack = [] 24 25 for i, height in enumerate([0] + heights + [0]): 26 while stack and stack[-1][0] > height: 27 rect_height = stack.pop()[0] 28 left = stack[-1][1] 29 area = (i - left - 1) * rect_height 30 max_area = max(area, max_area) 31 32 stack.append((height, i)) 33 34 return max_area 35 36 37# @leet end 38 39 40def test(): 41 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def largestRectangleArea(self, heights: list[int]) -> int: 5 """ 6 This question asks us to find the largest rectangle in a set of 7 heights. 8 9 We can do this in $O(n)$ time with $O(n)$ space, using a monotonic 10 stack. 11 12 We only want to keep the largest item we've seen so far on the stack, so 13 if we see an item that's larger than the top of the stack, we pop it 14 and immediately process it to see if it would create a larger rectangle 15 than currently exists. 16 After we're done processing those items, we add the current height + index to 17 the monotonic stack. 18 19 We also want to handle the edge case where either the start or end of heights 20 could contain the largest rectangle, so we add a [0] at both ends. 21 """ 22 23 max_area = 0 24 stack = [] 25 26 for i, height in enumerate([0] + heights + [0]): 27 while stack and stack[-1][0] > height: 28 rect_height = stack.pop()[0] 29 left = stack[-1][1] 30 area = (i - left - 1) * rect_height 31 max_area = max(area, max_area) 32 33 stack.append((height, i)) 34 35 return max_area
def
largestRectangleArea(self, heights: list[int]) -> int:
4 def largestRectangleArea(self, heights: list[int]) -> int: 5 """ 6 This question asks us to find the largest rectangle in a set of 7 heights. 8 9 We can do this in $O(n)$ time with $O(n)$ space, using a monotonic 10 stack. 11 12 We only want to keep the largest item we've seen so far on the stack, so 13 if we see an item that's larger than the top of the stack, we pop it 14 and immediately process it to see if it would create a larger rectangle 15 than currently exists. 16 After we're done processing those items, we add the current height + index to 17 the monotonic stack. 18 19 We also want to handle the edge case where either the start or end of heights 20 could contain the largest rectangle, so we add a [0] at both ends. 21 """ 22 23 max_area = 0 24 stack = [] 25 26 for i, height in enumerate([0] + heights + [0]): 27 while stack and stack[-1][0] > height: 28 rect_height = stack.pop()[0] 29 left = stack[-1][1] 30 area = (i - left - 1) * rect_height 31 max_area = max(area, max_area) 32 33 stack.append((height, i)) 34 35 return max_area
This question asks us to find the largest rectangle in a set of heights.
We can do this in $O(n)$ time with $O(n)$ space, using a monotonic stack.
We only want to keep the largest item we've seen so far on the stack, so if we see an item that's larger than the top of the stack, we pop it and immediately process it to see if it would create a larger rectangle than currently exists. After we're done processing those items, we add the current height + index to the monotonic stack.
We also want to handle the edge case where either the start or end of heights could contain the largest rectangle, so we add a [0] at both ends.
def
test():