Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4]
Output: 4
Constraints:
-
1 <= heights.length <= 105 -
0 <= heights[i] <= 104
SOLUTION:
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n = len(heights) next_lowest = [n for i in range(n)] prev_lowest = [-1 for i in range(n)] maxArea = 0 inc_stack = [] for i in range(n): while len(inc_stack) > 0 and heights[i] < heights[inc_stack[-1]]: curr = inc_stack.pop() next_lowest[curr] = i if len(inc_stack) > 0: prev_lowest[i] = inc_stack[-1] inc_stack.append(i) for i in range(n): currArea = (next_lowest[i] - prev_lowest[i] - 1) * heights[i] maxArea = max(maxArea, currArea) return maxArea # class Solution: # def largestRectangleArea(self, heights: List[int]) -> int: # n = len(heights) # maxArea = 0 # for i in range(n): # curr = heights[i] # left = i # right = i # while left >= 0 and heights[left] >= curr: # left -= 1 # left += 1 # while right < n and heights[right] >= curr: # right += 1 # right -= 1 # maxArea = max(maxArea, curr * (right - left + 1)) # return maxArea # class Solution: # def makeSeg(self, arr, i, j): # if (i, j) in self.seg: # return self.seg[(i, j)] # if i == j: # self.seg[(i, j)] = arr[i] # return arr[i] # mid = (i + j) // 2 # curr = min(self.makeSeg(arr, i, mid), self.makeSeg(arr, mid + 1, j)) # self.seg[(i, j)] = curr # return curr # def getMin(self, arr, i, j, ni, nj): # if ni >= i and nj <= j: # return self.seg[(ni, nj)] # if (ni < i and nj < i) or (ni > j and nj > j): # return float('inf') # mid = (ni + nj) // 2 # return min(self.getMin(arr, i, j, ni, mid), self.getMin(arr, i, j, mid + 1, nj)) # def largestRectangleArea(self, heights: List[int]) -> int: # self.seg = {} # n = len(heights) # if n == 1: # return heights[0] # self.makeSeg(heights, 0, n - 1) # mrec = float('-inf') # for i in range(n): # for j in range(i, n): # mrec = max(mrec, (j - i + 1) * self.getMin(heights, i, j, 0, n - 1)) # return mrec # class Solution: # def largestRectangleArea(self, heights: List[int]) -> int: # n = len(heights) # areas = [] # maxArea = float('-inf') # areas.append((0, heights[0])) # for i in range(1, n): # if heights[i] < areas[-1][1]: # maxArea = max(maxArea, (i - areas[-1][0]) * areas[-1][1]) # areas.pop() # areas.append((i, heights[i])) # return maxArea 
Top comments (0)