题目大意
给定一个柱状图，求它能包含的最大的矩形的面积。如下图中阴影部分就是要求的矩形。
输入: [2,1,5,6,2,3]
输出: 10
解题思路
栈，难题。
看了半天两个解法，只有下图最容易理解：
http://www.cnblogs.com/zuoyuan/p/3783993.html
https://shenjie1993.gitbooks.io/leetcode-python/084%20Largest%20Rectangle%20in%20Histogram.html
依次遍历柱状结构，如果是递增的则压栈，
如果不是则把比它高的柱依次弹出（只弹出比当前柱高的可以保证把当前柱压栈后，栈中的柱依旧是依次递增的）并计算以该柱为高的矩形的面积。
计算面积时，宽度应该是栈顶元素到遍历到元素之间的宽
如当弹出第二个2（2后面没有比它小的元素，为了使该元素能顺利弹出，在原柱状图末尾加一个0）时，栈顶元素是1，这样就能方便计算出宽度为4。还有一个问题是弹出1时栈中没有元素，无法计算宽度，所以在初始化时要在栈底加一个-1来应对所有元素都出栈的情况。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
stack=[]
i=0
area=0
while i<len(heights):
if stack==[] or heights[i]>heights[stack[len(stack)-1]]: # 递增直接入栈
stack.append(i)
else: # 不递增开始弹栈
curr=stack.pop()
if stack == []:
width = i
else:
width = i-stack[len(stack)-1]-1
area=max(area,width*heights[curr])
i-=1
i+=1
while stack != []:
curr = stack.pop()
if stack == []:
width = i
else:
width = len(heights)-stack[len(stack)-1]-1
area = max(area,width*heights[curr])
return area
|
总结
stack.pop()输出弹出的值