稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

秘密武器之单调栈

除了在树的遍历,DFS等常规场景使用栈(Stack)以外,针对某些特定的问题,还能以栈为主要手段进行非常巧妙的解题,栈中数据(通常是整数)的存储以单调递增或者单调递减的形式,新的元素入栈前通常要把小于它的或者大于它的元素出栈,习惯称之为单调栈

问题的常规解的时间复杂度通常会达到O(n2)或者O(nlogn),但使用单调栈可以达到O(n),思路非常的巧妙。

单调栈的特点

单调栈使用的数据结构就是栈,通常存储整数,可以入栈元素的下标,也可以直接把元素入栈。一般当需要计算元素之间的跨度时,比如像求面积,或者求天数时,这需要用元素的下标来计算,所以这时把元素下标入栈更为方便;其他情况直接入栈元素就可以。

单调栈,有二个重要的特性,一是栈,也要后进先出(FILO),二是单调性,栈中的元素要么是递增的要么是递 减的。具体就单调性而言分为两类:

  1. 单调递增栈:元素在栈中从栈底到栈顶是由大到小的,由此,出栈的序列是由小到大的,是递增的
  2. 单调递减栈:元素在栈中从栈底到栈顶是由小到大的,由此,出栈的序列是由大到小的,是递减的

为了保持单调性,在入栈的时候,需要把破坏单调性的元素出栈,直到能够保持单调性。

可能不同的文章对单调性定义不同,有些是以栈中的顺序为主,有些是以出栈的序列为主,但只是概念上的不同理解而已,本质上并不无差别。本文将以出栈序列来定义。

单调栈的适用性及其代码流程

单调栈利用后进先出和单调性能够在一个一维数组中选出一个『下一个更大元素』或者『下一个更小元素』的序列,从而实现某些问题的解。

代码流程

它的典型流程,以单调递增栈为例,是:

  1. 遍历输入列表(或者数组)
  2. 如果栈为空,或者当前元素(以下标形式或者元素)大于栈顶,直接入栈
  3. 否则,进行清栈:依据题目中某些约束条件,需要把栈中小于当前元素的元素出栈,然后把当前元素入栈
  4. 遍历完后,可能还需要清栈,栈中剩余的肯定 是不直接满足某些约束条件的,通常是对栈中元素直接以某些边界条件去计算结果

另外,在实战中,还可以使用『哨兵』来简化逻辑,通常作为栈底,比如把-1(具体的数值需要依题而定)放在栈底,那么判断栈是否为空时就需要检查 是否忆到了哨兵元素。

适用性

单调栈应用范围不算大,它仅适合解决NEG问题,即Next Greater Element,下一个更大元素。注意,这里也可以更小的元素,也可以是前一个。

以一个简单的例子来说明,比如,有一个数组nums = [2, 1, 2, 4, 3],返回一个等长数组,每个元素是当前索引在原数组中的『下一个更大』元素,如果没有就存-1。比如输入[2,1,2,4,3]就返回[4,2,4,-1,-1]

这是典型的NEG问题。暴力解法容易想到,二次遍历就能找到,但会达到O(n2)的复杂度。

单调栈就能派上用场:整体思路就是还没有找到『更大』元素的元素先入栈,约束条件就是『更大的元素』,清栈就是把栈中小于当前元素的元素都弹出,因为它们已找到了『更大』元素,具体的:

  1. 从前往后遍历,因为需要修改对应索引的值,所以栈中存索引比较方便
  2. 栈为空,或者当前元素[i]小于栈顶,就直接入栈
  3. 否则,清栈,把栈中小于当前元素出栈,因为它们忆找到『更大』元素了,就是当前元素[i]
  4. 遍历完成后,栈中可能有剩余元素,需要清栈,这些元素都没有找到『更大』元素的,直接存-1即可

明显,这里用的是单调递增栈。只遍历一次,所有元素最多只入栈一次,所以时间复杂度是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int[] result = new int[nums.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
    if (stack.isEmpty() || nums[stack.peek()] > nums[i]) {
        stack.push(i);
    } else {
        // 清栈
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
             result[stack.pop()] = nums[i];
        }
    }
}
// 清栈
while (!stack.isEmpty()) {
    result[stack.pop()] = -1;
}

同一套路

NEG是一类问题,用单调栈可解,但问题可能会被包装成各种问题,需要能够脱去外衣和内衣看到问题的本质。

比如,输入的是每日温度,找温度更高的一天,或者以身高为背景的问题,如只能看到比你矮的人的发型,如只能与比你矮的人交朋友等等。

典型题目

题目 题解 说明
42. 接雨水 题解
496. 下一个更大元素 I 题解
503. 下一个更大元素 II 题解
739. 每日温度 题解
84. 柱状图中最大的矩形 题解
85. 最大矩形 题解
768. 最多能完成排序的块 II 题解

参考资料

Comments