共计 2469 个字符，预计需要花费 7 分钟才能阅读完成。
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，代表栈为 null
int 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 记录指针以后地位。
写在最初
保护枯燥栈这种写法其实是很奇妙的，然而在求面积的题外面其实常常用到，除了这个题还有字节面试的那道接雨水也是。前面碰到面积相干的能够往栈这边想一下。