nathanwailes

LeetCode 84 - Largest Rectangle in Histogram - 2023.01.03 solution

Jan 3rd, 2023
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.10 KB | None | 0 0
  1. class Solution:
  2.     def largestRectangleArea(self, heights: List[int]) -> int:
  3.         """ How to solve it: To solve this in O(n) time, we want to think about what information
  4.        we need at each solution-relevant index in order to make the necessary calculation needed
  5.        to move towards the correct answer.  So, for example, in this case we want to be able to
  6.        calculate at each index-that-represents-a-possible-rectangle what that rectangle's area
  7.        is, so we can compare it to the max area we've found so far.  But the question is: how do
  8.        we decide what the relevant index is for each possible rectangle?  The answer is: a
  9.        possible rectangle is defined by its start and end, where the start is the rise to a new
  10.        height, and the end is a fall to a lower height.
  11.  
  12.        We'll want to calculate the size of the area of the rectangle when we arrive at its end.
  13.        So we'll need a data structure that will contain the starting index of each possible
  14.        rectangle.  Should it also contain the ending index?  Do we need to store the ending
  15.        indices?  I don't think we do, because we'll presumably already have stored all the
  16.        relevant starting indices for each ending index, so when we arrive at each ending index
  17.        we should be able to make whatever calculations we need to make and then never worry
  18.        about that ending index again.
  19.  
  20.        So we want to store possible starting indices in memory.  When can we forget about a
  21.        starting index?
  22.        """
  23.         possible_rectangles = []
  24.         max_area = 0
  25.         for i in range(len(heights) + 1):
  26.             curr = heights[i] if i < len(heights) else 0
  27.             current_height_start = i
  28.             while possible_rectangles and curr < possible_rectangles[-1][0]:
  29.                 prev = possible_rectangles.pop()
  30.                 current_height_start = prev[1]
  31.                 prev_rect_area = prev[0] * (i - prev[1])
  32.                 max_area = max(max_area, prev_rect_area)
  33.             possible_rectangles.append((curr, current_height_start))
  34.         return max_area
Advertisement
Add Comment
Please, Sign In to add comment