![LeetCode 刷题记录: 101. Symmetric Tree [Python]](/images/thumbnail.svg)
原题
https://leetcode.com/problems/largest-rectangle-in-histogram/
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.
思路
在height后面加上一个0作为右边界，记录高度堆栈stack加上一个-1作为左边界。
遍历heights，若当前height不低于stack最后一个元素的高度时，添加进stack中。否则：
从堆栈中弹出最后一个元素，即当前最高处位置信息，获取该位置的高度。
以当前位置i作为右边界，当前堆栈的最后一个元素stack[-1]，即当前第二高的位置作为左边界，宽度则为右边界-左边界-1（边界均不包含在内），即w=i-stack[-1]-1。
此时矩形面积即为h*w。
代码
1 | class Solution: |