Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def largestRectangleArea(self, heights: List[int]) -> int:
- """ How to solve it: To solve this in O(n) time, we want to think about what information
- we need at each solution-relevant index in order to make the necessary calculation needed
- to move towards the correct answer. So, for example, in this case we want to be able to
- calculate at each index-that-represents-a-possible-rectangle what that rectangle's area
- is, so we can compare it to the max area we've found so far. But the question is: how do
- we decide what the relevant index is for each possible rectangle? The answer is: a
- possible rectangle is defined by its start and end, where the start is the rise to a new
- height, and the end is a fall to a lower height.
- We'll want to calculate the size of the area of the rectangle when we arrive at its end.
- So we'll need a data structure that will contain the starting index of each possible
- rectangle. Should it also contain the ending index? Do we need to store the ending
- indices? I don't think we do, because we'll presumably already have stored all the
- relevant starting indices for each ending index, so when we arrive at each ending index
- we should be able to make whatever calculations we need to make and then never worry
- about that ending index again.
- So we want to store possible starting indices in memory. When can we forget about a
- starting index?
- """
- possible_rectangles = []
- max_area = 0
- for i in range(len(heights) + 1):
- curr = heights[i] if i < len(heights) else 0
- current_height_start = i
- while possible_rectangles and curr < possible_rectangles[-1][0]:
- prev = possible_rectangles.pop()
- current_height_start = prev[1]
- prev_rect_area = prev[0] * (i - prev[1])
- max_area = max(max_area, prev_rect_area)
- possible_rectangles.append((curr, current_height_start))
- return max_area
Advertisement
Add Comment
Please, Sign In to add comment