玩一玩单调栈

发表于 | 分类于

单调栈

2017年最后一篇博客，本来想取个引人入胜的题目，奈何文学修饰功力不够，还是算了吧。不废话了，本篇博客介绍了一种数据结构—单调栈，这个数据结构看似简单，用起来却有很大的能量。

Hello 单调栈!

什么是单调栈？顾名思义，单调栈首先是一个栈，并且栈内的元素的大小按照他们所在栈内的位置，满足一定的单调性。单调栈是一种理解起来很容易，但是运用起来并不那么简单的数据结构。那么到底什么时候用这个单调栈，怎么用单调栈呢？

首先，我们利用单调栈解决一个简单的问题：实现一个栈，带有出栈，入栈，取最小元素三个方法。要保证这三个方法的时间复杂度都是O(1)。

解决方案：利用单调栈，我们利用了2个栈，一个栈用于完成出栈，入栈，另一个辅助栈用于完成取最小元素的操作。

  1. 设原有的栈叫做栈A，此时创建一个额外的栈B，用于辅助原栈A。
  2. 当第一个元素进入栈A的时候，让新元素的下标进入栈B。这个唯一的元素是栈A的当前最小值。（考虑到栈中元素可能不是类对象，所以B栈存储的是A栈元素的下标）
  3. 每当新元素进入栈A时，比较新元素和栈A当前最小值的大小，如果小于栈A当前最小值，则让新元素的下标进入栈B，此时栈B的栈顶元素就是栈A当前最小值的下标。如果大于栈A当前最小值，那么就不操作。
  4. 每当栈A有元素出栈时，如果出栈元素是栈A当前最小值，则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的，是栈A当中原本第二小的元素，代替刚才的出栈元素成为了栈A的当前最小值。
  5. 当调用getMin方法的时候，直接返回栈B的栈顶所指向的栈A对应元素即可。

以上，我们就利用单调栈实现了一个最小栈。当然，单调栈的功能远不止这些，我在刷LeetCode的过程中也总结了有关于单调栈的题目。

503.Next Greater Element II

问题描述：给定一个循环数组(数组的最后一个元素的后继是数组的第一个元素)，按照遍历的方向(从左往右)找到数组中每个元素的第一个比自身大的元素，如果找不到，则该元素位置的值为-1.

我翻译的很挫，还是贴上LeetCode的原本的描述吧。
Description: Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.

如果不够明白题目的意思，就多看看例子，我直接把LeetCode上的example搬运过来了：
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1’s next greater number is 2;
The number 2 can’t find next greater number;
The second 1’s next greater number needs to search circularly, which is also 2.

解法: 利用单调栈(保证栈中元素是单调减)，并且栈中保存原数组索引，这样比保存数值要方便很多，因为通过数组的索引可以得知对应的数组元素的值，而通过数值是无法得知索引的。遍历两次数组，因为本题是循环数组，对于当前访问的元素，压入栈内，并且在压入元素的时候，调整栈中元素，直到栈内元素是递减的，在调整栈中元素的过程中就能找到当前元素在遍历方向上第一个大于自身的元素了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] nextGreaterElements(int[] nums) {
    Deque<Integer> stack = new ArrayDeque<>();//在单线程中利用双端队列作为栈的实现方法，要比Vector(线程安全，会resizing)效率高很多。
    int[] res = new int[nums.length];
    //初始化
    for (int i = 0; i < res.length; i++) {
        res[i] = -1;
    }
    //遍历2次数组元素即可，利用栈操作来模拟算法执行的过程
    for (int i = 0; i < 2 * nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i % nums.length]) {
            res[stack.pop()] = nums[i % nums.length];
        }
        stack.push(i % nums.length);
    }
    return res;
}

我们在单线程环境下用栈，最好使用双端队列的实现，而不要用Vector(jdk默认使用Vector实现Stack)，这样会提高效率。
无独有偶，LeetCode中还有一道类似的题目，区别只是将循环数组变成了非循环数组，那么我们就只用遍历一次数组了。传送门：LeetCode 739.Daily Temperatures解法：参考解法

84.Largest Rectangle in Histogram

问题描述：这次就不翻译了，直接上LeetCode的描述。

Description: 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.
For example,
Given heights = [2,1,5,6,2,3],
return 10.

解法: 先上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int result = 0;
    for (int i = 0; i < heights.length; i++) {
        while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
            int h = heights[stack.pop()];
            result = Math.max(result, h * ((stack.isEmpty() ? i : i - stack.peek() - 1)));
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        int h = heights[stack.pop()];
        result = Math.max(result, h * ((stack.isEmpty() ? heights.length : heights.length - stack.peek() - 1)));
    }
    return result;
}

解析：我们要找到最大的长方形面积，可以按照这种方式来找：对于数组中每个元素代表的高度，找到以当前这个高度为高的最大的长方形面积，那么遍历所有的高度即可。我们直接暴力求解的话，就是O(n^2)的复杂度。

有了上述思路，我们就可以用单调栈来优化了。我们在遍历数组的时候维护一个栈,这个栈中的元素从底向上按照高度值递增.如果遇到当前bar的高度比栈顶元素低，那么就出栈直到栈顶元素低于当前bar的高度。关键就在这里，当我们将第i个元素弹出栈的时候，我们就可以计算以heights[i]为高的最大长方形的面积。在遍历完数组之后，栈内元素仍然需要继续弹出，最后所有元素都会依次出栈,意味着计算完了所有可能的最大面积,就可以得到结果了。

再来分析一下这个算法的可行性：每一个元素都要入栈一次，出栈一次。入栈的时候的是遍历访问到它的时候，那出栈的时候意味着什么呢。在这里元素出栈意味着，我们已经计算了以它的高度为高的最大长方形面积。结合栈内元素的单调性，栈顶元素所对应的bar一定比出栈元素对应的bar小，所以以出栈元素对应的bar为高的长方形无法往左边延展。结合代码，我们已经判断过当前处理的第i个元素所对应的bar也比出栈元素对应的bar小，所以长方形无法往右边延展。这个元素和左右边界之间如果还有空隙，那么这些空隙里所存在的bar，一定是因为维护栈的单调性而被弹出了。也就是说，如果这些bar存在，那么一定比这个出栈元素所对应的bar高。既然这些bar的高度更高，那么就可以被纳入这个最大长方形面积的计算中，也就不影响当前出栈元素的最大长方形面积的计算。以上我们就证明了，当我们将第i个元素弹出栈的时候，我们计算了以heights[i]为高的最大长方形的面积。简直因吹斯汀！

与本题相关的，还有LeetCode 85.Maximal Rectangle，以及参考解法

总结

看了以上两个例子，单调栈看似简单，真正用好却还是有点难度。这里强行总结一下吧，单调栈通常应用在一维数组上，如果遇到的问题，和前后元素之间的大小关系有关系的话，例如503题中我们要找比某个元素大的元素，84题中前后的bar的高低影响了最终矩形的计算，我们可以试图用单调栈来解决。在思考如何使用单调栈的时候，可以回忆一下这两题的解题套路，然后想清楚，如果使用单调栈，并且要想好每个元素出栈时候的意义。

0%