Largest Rectangle in Histogram - LeetCode
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
- code
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# maintain a strictly increasing stack, so we know the leftmost easily
stack = [-1] # if empty, when we pop out the first element, we can't calculate the width easily
res = 0
for i in range(len(heights)):
while stack[-1] != -1 and heights[i] <= heights[stack[-1]]:
# pop out stack[-1] and calculate its max area
cur_height = heights[stack.pop()]
cur_width = i - 1 - stack[-1] # not include the bar at i
res = max(res, cur_height * cur_width)
stack.append(i)
# to the rightmost already
while stack[-1] != -1:
cur_height = heights[stack.pop()]
cur_width = len(heights) - 1 - stack[-1]
res = max(res, cur_height * cur_width)
return res
- code
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = [-1]
res = 0
heights.append(-1) # force to pop out all in the end
for i, v in enumerate(heights):
while stack[-1] != -1 and v <= heights[stack[-1]]:
cur_height = heights[stack.pop()]
res = max(res, cur_height * (i - stack[-1] - 1))
stack.append(i)
return res