# leetcode: 84. Largest Rectangle in Histogram -开发者知识库

## Problem

``````# 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.
#
# For example,
# Given heights = [2,1,5,6,2,3],
# return 10.``````

### Idea

``````仔細考察Brute Force算法，發現問題在於指針重復掃描。以遞增序列為例：

0 1 2 3 4 5 6

1. 利用這個性質，可以將遞增序列cache在一個stack中，一旦遇到遞減，則根據h[j 1]來依次從stack里pop出那些無法繼續擴展的bar k，並計算面積。

2. 由於面積的計算需要同時知道高度和寬度，所以在stack中存儲的是序列的坐標而不是高度。因為知道坐標后很容易就能知道高度，而反之則不行。``````

## AC

``````class Solution():
def largestRectangleArea(self, xs):
xs.insert(0, 0)
xs.append(0)
stack, maxArea = [], 0
for i, x in enumerate(xs):
if not stack or xs[stack[-1]] <= x:
stack.append(i)
else:
while stack and xs[stack[-1]] > x:
maxArea = max(maxArea, xs[stack[-1]]*(i-stack[-2]-1))
stack.pop()
stack.append(i)
right = stack[-1]
stack.pop()
while len(stack) > 1:
offset = right-stack[-1]
maxArea = max(maxArea, xs[stack[-1]]*offset)
stack.pop()
return maxArea

if __name__ == "__main__":
assert Solution().largestRectangleArea([2, 0, 2]) == 2
assert Solution().largestRectangleArea([2, 1, 5, 6, 2, 3]) == 10``````

0条回复