单调栈真的蛮好用的呢～

发布: 分类: 评论次数： 阅读次数： 本文字数： 4.1k

又是一天枯燥无味的课，上午是憨批的学术英语，晚上是听不进去的并行计算，下午也就把目前正在记录的这道题稍微看了看，至于为啥要写点东西记下来呢？因为这种算法思路我好像并不常有，就比如上次那个删除重复值的思路（双指针那个），我同样也不怎么能想得到，所以呢，就笔头勤点，写下来可以经常看看，老话说得好，熟练于心嘛～

现在已经是晚上23点以后了，别问我为啥到现在还没睡，原因很简单，因为我现在还不想睡，我的手机正在forest上种树呢，所以即使我现在到床上去也只能在手机上看天气之类的应用（推荐forest，下次给大家伙看看我的森林，可以摆脱手机控～），所以呢，就随便写写，反正也只是未来的自己看看……..

终于硬是扛到了0点以后了，好了，不写了，明天上午等我爬起来之后再继续写吧，，其实也就是适当地拿leetcode上的一道题来讲一下单调栈的使用，以及它究竟可以用来做些什么。从名字上来看，这是一个栈，并且栈中的元素应该都是单调放入的。

题目介绍

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

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

示例：

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

思路

其实呢，这道题拿到手后，我第一想到的就是：我去，这道题咋这么眼熟，之前好像也在哪看过这歌柱状图，想了好长时间才想起，原来是之前做的那道接雨水的题。。。

然后呢，我连暴力解法都没想起来，这就是越做题越倒退嘛？？

暴力解法

自己想一想，暴力解法也不是很难，思路比较直接，既然是要寻找面积最大的矩形，那就以每根柱子为开始，向两边延伸（延伸：指以当前柱子高度往左右画条水平线，直到左右都有柱子高度没有达到水平线结束）

简单点来说，就是对每个柱子往左往右找到第一个小于自己高度的柱子，以举例来说，heights[4] = 2，往左比其小的第一个是heights[1]，往右则是没有比其小的；

代码我就不写了，因为很简单，至于找第一个最小的要么直接遍历要么二分法查找都是可以的。

单调栈—两次遍历

单调栈的含义已经在前面说过了，这里不作解释；至于这道题为什么能牵扯到单调栈，可以思考下面这句话：

如果柱子从左到右是单调增高的，那么对任何一个柱子而言，其左边第一个比其小的就是它的左侧邻居；那么如果有一个数据结构，能够保存这些柱子（不是单调增高的）中那些逐渐变高的柱子index的话，针对当前处理的柱子，想要找到它左侧第一个小于它的柱子就会很简单（因为保存的数据中只要最后一个index的高度小于当前柱子高度，那它就是答案，否则依次往前找到比当前柱子高度小的即可）。

注意：这里的单调是严格单调，下面还会有方法里的不是严格单调

至于标题中的两次遍历，想必大家也都明白为啥是两次（额，其实就是找到左边边界与右边边界）

还是以示例来解释下操作流程（2，1，5，6，2，3）：

  • 首先我们需要两个结构来保存每根柱子的左边界与右边界，简单记为left与right（这里记录的是下标索引，也可以直接记录高度）
  • 处理第一根柱子，高度为2，它左边没有柱子，因此为了计算面积方便统一，我们给其左边界赋值为-1（哨兵），并将第一根柱子的下标索引0放入我们用来保存递增index的结构—单调栈，目前栈内为【0】，left为【-1】
  • 处理第二根柱子，高度为1，这时单调栈的作用就可以看见了，我们用当前柱子高度1与栈顶的柱子高度（2）比较，发现栈顶柱子比当前柱子高，那栈顶的肯定不是当前柱子的左边界（用最笨的话解释左边界：[1，2，5，3，4]，3的左边界是2），既然不是，就把栈顶的柱子丢了，看下一个栈顶是不是左边界，结果发现，丢完后，栈空了，这就表明当前柱子没有左边界，和第一根柱子一样，我们给其left[1]赋值为-1，并将当前柱子下标1入栈，目前栈内为【1】，left为【-1，-1】
  • 处理第三根柱子，高度为5，栈顶柱子高度为1，由于当前柱子高度大于栈顶的，所以栈顶的就是当前柱子的左边界，将栈顶的下标值赋予当前柱子left之后，将当前柱子下标入栈，目前栈内为【1，2】，left为【-1，-1，1】
  • 以此类推可以得到：left为【-1，-1，1，2，1，4】
  • 按照同样的方法，从右往左遍历一次，可以得到：right为【6，6，4，4，6，1】，注意：这里的6也是哨兵
  • 计算结束后，就是统计最大矩形面积，这时，只需要计算以每根柱子往左右延伸的最大面积即可，举个简单的例子，第三根柱子高度为5，它的左边界为1，右边界为4，因此，面积就是（4 - 1 - 1） * 5 = 10，以此类推即可获得最大矩形面积

关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    //初始化哨兵
    stack.push(-1);
//从左往右遍历
    for(int i = 0; i < len; i++){
        if(stack.peek() == -1){
            left[i] = -1;
        }else{
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            left[i] = stack.peek();
        }
        stack.push(i);
    }

    //从右往左遍历
    stack.clear();
    stack.push(len);
    for(int i = len - 1; i >= 0; i--){
        if(stack.peek() == len){
            right[i] = len;
        }else{
            while (stack.peek() != len && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            right[i] = stack.peek();
        }
        stack.push(i);
    }

单调栈—遍历一次

上面的思路会遍历两次，那是不是可以只遍历一次呢，答案是可以的，其实很明显，上面遍历两次是因为我们需要获得left与right，那是不是只要在获得left的同时，获得right不就好了吗，确实是这样，下面遍历一次的思路，需要了解下面这段话：

假设我们正在处理heights[i]，这时通过判断（heights[i]小于等于栈顶的高度），所以按照上面那种方法思路，是不是需要将栈顶的pop出来，没错吧～那对于栈顶的值来说，可不可以认为当前的heights[i]就是其右边界呢？首先需要明确，当前的i与栈顶值之间是不存在一个j（栈顶值<j<i），使得heights[j]小于等于栈顶的高度的，因为如果存在，那么在处理heights[j]时，栈顶的那个值早已经被pop了，所以可以理解成，i是栈顶值右侧第一个在高度上小于等于它的值（注意是小于等于）

还是举个简单的例子吧，[2，3，1，5，5，5，6，2]

当我们处理第一个5的时候，栈内是【2】，我们可以顺利得到这个5的左边界为2，对于栈顶的2我们暂时没法得到其“右边界”，因为它还没有到被弹出去的时候（记住这里），第一个5处理完后将其入栈，栈内为【2，3】，处理第二个5时，我们发现栈顶的高度和其是相等的，因此，是需要被弹出的（因为这里是严格单调的，即栈内不存在相等的值），既然栈顶的值要被弹出了，所以按照上述的分析我们可以得到栈顶值的“右边界”就应该是第二个5，不知道你们有没有发现，这里对于栈顶的5而言，它所获得的“右边界”是不对的，因为其真实的右边界应该是最末尾的那个2。

所以呢，这里对于第一个5，我们没有获得真实的右边界，这样会影响答案吗？实际上，自己想一想，究竟什么时候会获得不真实的右边界呢？只有当当前处理的值与栈顶值是相等的时候才会赋予栈顶值不真实的右边界，既然这样，那针对当前的值而言，只要后面会出现一个小于它的值（也就是当前的值需要被pop的时候），它就可以获得真实的右边界，而当前值与最初栈顶与其相等的那个值真实意义上能获得的最大矩形面积是相等的。

举例来说，当第二个5处理完入栈后，栈内为【2，4】，第三个5依旧与栈顶值相等，所以对于栈顶的值，也就是第二个5而言，依然会获得不真实的右边界（第三个5），第三个5处理完后，入栈，栈内为【2，5】，当处理6的时候，正常处理，栈内为【2，5，6】，处理最后一个2时，栈顶值的高度为6，所以需要被pop，那6的右边界就是当前处理的2，pop后，栈顶变为5，其高度值也为5（第三个），依旧需要被pop，所以第三个5的右边界就是最后一个2（真实的右边界），总之，三个5，只有最后一个5会获得真实右边界，不过这三个5所能获得的最大矩形面积是相等的，所以并不影响最终的答案。

也就是说，这里的左边界一定是真实的，右边界不一定真实，不过不影响最后结果

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int largestRectangleArea(int[] heights){
    int len = heights.length;
    int[] new_height = new int[len + 2];
    for(int i = 1; i <= len; i++){
        new_height[i] = heights[i - 1];
    }

    Deque<Integer> stack = new ArrayDeque<>();

    int[] left = new int[len + 2];
    int[] right = new int[len + 2];

    for(int i = 0; i < len + 2; i++){
        while (!stack.isEmpty() && new_height[stack.peek()] >= new_height[i]){
            int temp = stack.pop();
            right[temp] = i;
        }
        left[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
    }

    int ans = 0;
    for(int i = 1; i < len + 1; i++){
        ans = Math.max(ans, new_height[i] * (right[i] - left[i] - 1));
    }
    return ans;
}

注意代码中有步操作：将原数组中的值移到了新数组中，也就是在原数组前后各加了个0，意义如下：

前面的0: 保证数组中所有的值都是大于等于它的，其实在上述代码中，可以没有前面这个0，这里加个0是因为其实可以没必要将left与right的值保存起来再来计算，为什么呢，不知道你有没有发现，每次需要弹出的时候，对于弹出的那个值而言，它的左边界与“右边界”（不真实，无影响）都是知道的了，那么为什么不可以直接计算它的最大面积呢？而加的这个前置0就是为了当栈内只有一个真实有效的值的时候，并且它需要被弹出，这时可以直接计算它的最大面积，因为即使弹出后，栈顶依旧有值而不是栈空，这时或许有人会问，那会不会前置0也被弹出呢？会，只有当遇到0的时候，不过没关系，因为这时对于栈顶的0而言，计算出来的值一定是0，不影响结果，不过还是需要判断下栈空，因为0弹出后stack.peek()是会报错的。

后面的0: 保证最后栈内所有有效值都会被弹出，以获得其右边界

不知道大家有没有注意到，我们的栈内是不允许有重复值的，也就是严格单调的，但其实呢，单纯单调的话也是可以计算的，只是这时获得的左边界不一定是真实的而已，与上面是一样的原因，也不会影响最终结果。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int largestRectangleArea(int[] heights){
    int len = heights.length;

    Deque<Integer> stack = new ArrayDeque<>();

    int[] new_height = new int[len + 2];
    for(int i = 1; i < len + 1; i++){
        new_height[i] = heights[i - 1];
    }

    int ans = 0;
    for(int i = 0; i < len + 2; i++){
        while (!stack.isEmpty() && new_height[stack.peek()] > new_height[i]){
            int temp = stack.pop();
            ans = Math.max(ans, new_height[temp] * (i - stack.peek() - 1));
        }
        stack.push(i);
    }
    return ans;
}

这里就没有将边界值保存起来，而是每次只要栈顶值会弹出时，直接计算栈顶的最大面积，因此，我们必须保证所有的值都会出栈，所以才会在原数组后面加个0（0一定小于任何有效值）；除此之外，while循环中的判断条件将>=改为了>，表示，栈内是可以保存连续重复值的。

哨兵值的使用，会使程序很大程度上简洁，比如说，如果上面的代码中，没有哨兵值（前后的0），那么我们在计算ans之前必须判断栈是否为空，必须手动将最后栈内的所有值弹出并计算最大面积。因此，哨兵值的使用很重要～

除此之外，计算对象的选择，也是很重要的，像我上面两种方式，一个计算对象是当前的heights[i]，一个是heights[stack.peek()]，前者必须将所有的left与right计算完才能计算，后者只需要在栈顶被弹出的时候就可以计算

其实呢，我们也可以在保持左边界一定真实的情况下，计算栈顶最大面积，只不过这种情况下需要判断栈空而已。

结束

在java中，能用Deque的时候尽量别用stack，因为你会这样：

用时长的就是stack，短的就是deque，优劣一眼就可以看出来～

写点有点多了，很多都是废话，只是给笨笨的博主当备忘录而已～