給定 n 個(gè)非負(fù)整數(shù)奋岁，用來(lái)表示柱狀圖中各個(gè)柱子的高度思瘟。每個(gè)柱子彼此相鄰，且寬度為 1 闻伶。
求在該柱狀圖中滨攻，能夠勾勒出來(lái)的矩形的最大面積。
image.png
`
以上是柱狀圖的示例蓝翰，其中每個(gè)柱子的寬度為 1光绕，給定的高度為 [2,1,5,6,2,3]
image.png
`
圖中陰影部分為所能勾勒出的最大矩形面積，其面積為10;個(gè)單位畜份。
示例:`
輸入: [2,1,5,6,2,3]
輸出: 10`
思路：
用一個(gè)單調(diào)遞增的棧來(lái)放bar诞帐，如果是遞增的就放進(jìn)棧，那么當(dāng)前bar的左邊界就是前一個(gè)元素（比當(dāng)前bar高度低的元素）爆雹，循環(huán)數(shù)組的時(shí)候停蕉，遇到高度比棧頂bar高度低，說(shuō)明找到了棧頂bar的右邊界钙态，高度就是棧頂bar高度慧起，寬度就是右邊界-左邊界（數(shù)組當(dāng)前位置到棧bar前一個(gè)位置的距離，即i-stack[-2]-1）册倒。每找到一個(gè)小于棧頂高度的需要循環(huán)和棧內(nèi)元素做判斷并計(jì)算最大面積蚓挤，計(jì)算完最大面積就彈出棧。height隊(duì)尾放入0是為了方便計(jì)算寬度驻子，同時(shí)0高度最低灿意，會(huì)把棧內(nèi)元素面積都計(jì)算完。stack放入-1是為了方便計(jì)算左邊界拴孤。`
參考圖如下，不完全相同
image.gif
`
class Solution:
def largestRectangleArea(self, heights):
# 在隊(duì)尾加一個(gè)0方便計(jì)算寬度
heights.append(0)
# 新增一個(gè)單調(diào)遞增棧放矩形
stack = [-1]
area = 0
for i in range(len(heights)):
# 如果當(dāng)前bar的高度height[i]低于棧頂bar高度甲捏，說(shuō)明棧頂bar找到右邊界演熟，且由于是單調(diào)遞增棧，棧頂前一個(gè)bar為左邊界stack[-2]，則可以計(jì)算當(dāng)前高度最大面積
while heights[i] < heights[stack[-1]]:
# 高度為棧頂bar高度
h = heights[stack[-1]]
# 寬度為左右邊界
w = i - stack[-2] - 1
area = max(area, h * w)
# 計(jì)算完最大面積后就彈出棧
stack.pop()
# 如果當(dāng)前bar的高度height[i]大于等于棧頂芒粹，說(shuō)明棧頂bar還沒(méi)找到右邊界兄纺，繼續(xù)放入棧
stack.append(i)
return area
su = Solution()
heights = [2, 1, 2]
res = su.largestRectangleArea(heights)
print(res)
