LeetCode第84题，使用枯燥递增栈求柱状图的最大面积，这个思维还是很奇妙的，记录下解题思路。

先看下题：

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

求在该柱状图中，可能勾画进去的矩形的最大面积。

示例:

输出: [2,1,5,6,2,3]
输入: 10

其实我没看题解之前我是齐全懵逼，间接用暴力法求解，而后超时。前面看完题解之后才意识到既然还能用栈去解，想出这个解法的人真的对栈这种数据结构了解的太通透了。

然而当你看懂其实思路还是很简略的。

请跟着我的思路一起看下这个后果是怎么进去的，要求柱状图面积，那肯定须要晓得左右边界和高度，咱们先手动保护一个枯燥递增的栈。这个栈能有什么用呢？

它会有一个个性，当第一个小于栈顶元素呈现时，咱们能算出栈里所有比以后元素大的以栈顶元素为右边界的这个柱子的最大面积，左边界怎么算呢，就是第二个栈顶元素+1，高度就是左右边界的最小高度。值为什么能这么算呢，因为栈是递增的，如果有比第二个栈顶元素小的元素时，它肯定是被弹出去了。（这个可能有点不那么好思考，倡议多写几遍或者debug一下）

接下来看下代码：

int len = heights.length;int maxArea = 0;Stack<Integer> stack = new Stack<>();//这里能等于n的起因是当i=n-1的时候栈里还会有最初一个元素，因而须要结构一个最小的n把栈里残余其余元素拿进去for (int i = 0; i <= len;) {    //等于n须要非凡解决    int h = (i == len ? 0 : heights[i]);    //保护一个枯燥递增栈，如果压栈元素比栈顶元素大，间接压入栈中，否则顺次将比它大的元素取出    if (stack.isEmpty() || h >= heights[stack.peek()]) {        stack.push(i);        i++;    }else {        int curHeight = heights[stack.pop()];        int rightBoundary = i - 1;        int leftBoundary = stack.isEmpty() ? 0 : stack.peek() + 1;        int width = rightBoundary - leftBoundary + 1;        maxArea = Math.max(maxArea, (curHeight * width));    }}return maxArea;

解释下这块代码，咱们一开始初始化了一个栈，和一个最大值，而后开始遍历柱子。

留神这里的 for (int i = 0; i <= len;) 是没有i++,i–这种迭代条件的，为啥呢，因为这里只有在压栈的时候须要下标前移，如果出栈的话下标是不会动的。当然你也能够写成for (int i = 0; i <= len;i++)，那外面的else局部代码就须要写成while循环，以保障出栈计算面积的时候指针不会挪动，看本人代码爱好吧，我看这种if,else感觉更清晰点。

而且这里的i是能到n的，这样相当于循环了n+1次，这样是为了将最初的栈里元素出栈做的非凡操作。

当i==n的时候，h就是0，代表一个最小值，而后把栈外面的元素全副压出来，否则就是失常的height[i]值。

入栈的条件是栈为空或者栈顶元素小于等于height[i]，压栈之后指针要后移。

当栈顶元素比height[i]大的时候，就能够计算柱状图的面积了，高度就是height[stack.pop()]，右边界i-1，左边界依据栈是否为空，空就是0，否则就是下一个栈顶元素+1,留神这时候第一个栈顶元素曾经弹出来了，

留神面积是right-left+1，这个你看柱状图就能看进去，比方6-5=1,其实是5,6两根柱子，所以要+1。

而后面积就是height[stack.pop()]*(right-left+1),在用max每次拿到最大值即可。

其实你写多了感觉这个实现不是很难，难的是能把这个办法想进去的人。

下面是应用的零碎自带的双端队列作为栈，然而因为做了肯定的封装，其实效率并不高，因而在LeetCode提交时能战胜的人其实不多，只有25%如同。

那咱们来优化一下，25的确太低了。

优化的点是什么呢？你须要先记住一个论断，我LeetCode刷这么多题总结的一个教训是，大部分时候数组去实现都会将效率晋升很多，前面在做递归的时候，用数组代替Set和map能显著晋升效率。

上面是我用数组实现的栈代替零碎自带的栈，而后将执行工夫胜利有43ms优化到了7ms，一下击败了99%的人，能够看出差别真的很大。

int n = heights.length;int max = 0;int[] stack = new int[n + 1];//记录栈顶元素的下标,因为零碎的stack是封装好的，stack.pop()和stack.peek()会主动拿栈顶元素//而咱们本人实现的时候须要去用一个变量记录栈顶元素下标，初始值为-1，代表栈为nullint top = -1;for (int i = 0; i <= n; ) {    int h = i == n ? 0 : heights[i];    if (top == -1 || h >= heights[stack[top]]) {        stack[++top] = i;        i++;    } else {        int high = heights[stack[top--]];        int right = i - 1;        int left = top == -1 ? 0 : stack[top] + 1;        int v = high * (right - left + 1);        max = max < v ? v : max;    }}return max;

这里入栈出栈没什么说的，都是指针的挪动而已，惟一须要留神的是，因为咱们初始化的是一个数组，且曾经有初始空间了，咱们不能用stack==null去判断数组是否为null，因而须要一个标记位去记录数组是否为空，我这里用的top这个int变量去示意的，这样一个益处是即能够判断是否为空，还能够用top记录指针以后地位。

写在最初

保护枯燥栈这种写法其实是很奇妙的，然而在求面积的题外面其实常常用到，除了这个题还有字节面试的那道接雨水也是。前面碰到面积相干的能够往栈这边想一下。