难度: Hard
原题连接
内容描述
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Example:
Input: [2,1,5,6,2,3]
Output: 10
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
参考大神learnjava的解法
All these problems share the same pattern: how to find the next greater/smaller element in an array.
Problem 84:
For bar i in the heights array, if we can find the first smaller bar with index l on the left
and the first smaller bar with index r on the right, then the current max area with h(i)
as the height is h(i)*(r-l-1). So we just need to compare all these current max areas.
To find l for each bar, we can use one stack (see problem 496, 503 and 739);
similarly we can use another stack for r.
beats 69.90%
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
left_stack, right_stack = [], []
left_indexes, right_indexes = [-1] * len(heights), [len(heights)] * len(heights)
for i in range(len(heights)):
while left_stack and heights[i] < heights[left_stack[-1]]:
right_indexes[left_stack.pop()] = i
left_stack.append(i)
for i in range(len(heights)-1, -1, -1):
while right_stack and heights[i] < heights[right_stack[-1]]:
left_indexes[right_stack.pop()] = i
right_stack.append(i)
res = 0
for i in range(len(heights)):
res = max(res, heights[i]*(right_indexes[i]-left_indexes[i]-1))
return res思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******
刚才是two-pass，现在优化成one-pass，beats 95%
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
heights.append(0)
area, stack = 0, [-1]
for idx, height in enumerate(heights):
while height < heights[stack[-1]]:
h = heights[stack.pop()]
w = idx - stack[-1] - 1
area = max(w*h, area)
stack.append(idx)
return area