leetcode 84 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。



---

• 我们维护一个栈，栈中的元素保持递减的关系

• 当我们遇到一个数nums[i] 如果nums[i]小于栈顶的元素，这就意味着，对于栈顶元素，他能组成的最大的矩形的左边界为栈中的栈顶元素的前一个元素，右边界为当前的i。这样一来，我们先把当前的栈顶元素pop出来，得到h此时的栈顶元素能够组成的最大的矩形面积为nums[h]*(i-1 - stack[-1])。

• 这么遍历完一遍之后，stack中可能存在还有元素的情况。那么此时，由于数组已经遍历完毕，对于栈中的所有元素，他的左边界为栈中它前面的一个元素，右边界为整个数组的长度。