原题
给出的n个非负整数表示每个直方图的高度，每个直方图的宽均为1，在直方图中找到最大的矩形面积。
给出 height = [2,1,5,6,2,3]，返回 10 (5 * 2)
解题思路
- DP一般是把n!/nn/2n优化到n2/n3，而本题暴力解法是n^2，我们希望优化到n，不是DP的强项
- n^2 -> n （stack强项）
- 求出把每个柱子当做最小的得到的面积 -> 求出n个值，取min
- 通过维护一个升序stack，实现 -> 找到每个数左边第一个比它小的和右边第一个比它小的
# push 2
stack = [] -> [2]
# push 1 ,以为2 > 1，所以pop 2以维持升序stack
# 2左边第一个比它小的就是none，右边第一个比它小的就是1
stack = [2] -> [1]
- Conditional Operator in Python
# Java version
a > 10 ? b : c
# Python version
b if a > 10 else c
完整代码
class Solution(object):
def largestRectangleArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height:
return 0
res = 0
stack = []
height.append(-1)
for i in range(len(height)):
current = height[i]
while len(stack) != 0 and current <= height[stack[-1]]:
h = height[stack.pop()]
w = i if len(stack) == 0 else i - stack[-1] - 1
res = max(res, h * w)
stack.append(i)
return res
