重温数据结构与算法之单调栈_单调栈的时间复杂度

前言

单调栈（monotonous stack）是指栈的内部从栈底到栈顶满足单调性的栈结构。 其实单调栈就是“栈 + 维护单调性”，根据元素依次增大/减小可分为两种

• 递增单调栈：栈中元素从栈底到栈顶依次增大
• 递减单调栈：栈中元素从栈底到栈顶依次减小

单调栈通常用来解决这种问题：给出n个数，用 O(n) 的时间求出每个数左/右边第一个比它小/大的数．

一、暴力法

1.1 遍历

使用暴力法就是对n个数进行遍历，找到需要的数，n个数需要进行n次，所以时间复杂度为$O(n^2)$。

以求出每个数右边第一个比它大的数的下标(没有为-1) 为例，用暴力法遍历

例子：8个数字 8, 7, 0, 1, 2, 9, 3, 5 来演示暴力法

• 第0轮：依次拿7,0,1,2,9和8对比得到9的索引5
• 第1轮：依次拿0,1,2,9 和7对比得到9的索引5
• 第2轮：依次拿1 和0对比得到1的索引3
• 第3轮：依次拿2 和1对比得到2的索引4
• 第4轮：依次拿9 和2对比得到9的索引5
• 第5轮：依次拿3,5 和9对比没有比9大的，为-1
• 第6轮：依次拿5 和3对比得到5的索引7
• 第7轮：5为最后一个数字，为-1

写成代码就是

int n = nums.length;
int [] ans = new int[n];
Arrays.fill(ans, -1);
for (int i = 0; i <  n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (nums[j] > nums[i]) {
            ans[i] = j;
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

1.2 优化思路

从上面遍历的过程中，可以看到是从左到右进行遍历，由于是找出右边第一个大的数，所以想从右边遍历到左边

for (int i = n - 1; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
        if (nums[j] > nums[i]) {
            ans[i] = j;
            break;
        }
    }
}
1
2
3
4
5
6
7
8

思路一：每次都要从i+1遍历到n, 是否能够保存之前的数据，处理一下就能得到自己想要的

思路二：8, 7, 0, 1, 2, 9, 3, 5 从5开始往左遍历，到2及之后，之前的数据9,3,5中的3,5完全没用，可以舍弃掉，当遍历到7时，0,1,2又可以舍弃掉，这似乎有种规律

二、使用单调栈

2.1 特点

由暴力法优化思路拓展开来，其实实现这种规律的数据结构就是单调栈，维持栈内元素的单调性，像上面就是递减单调栈，保持栈底最大，不断将栈顶元素小于将入栈的值出栈，最终栈顶剩的值就是第一个比要入栈的值大的元素，也就是所要求的值。

栈具有先进后出的特点，如果有新的元素入栈，单调栈调整过程中会将所有破坏单调性的栈顶元素出栈，并且出栈的元素不会再次入栈 。由于每个元素只有一次入栈和出栈的操作，所以使用单调栈的时间复杂度是$O(n)$

2.2 实现

由上面思路可以拓展的实现是从右到左

int n = nums.length;
int [] ans = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = n - 1; i >=  0; i--) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        stack.pop();
    }
    ans[i] = stack.isEmpty() ? -1 : stack.peek();
    stack.push(i);
}
1
2
3
4
5
6
7
8
9
10

实际还有另一种思路，从左到右

int n = nums.length;
int [] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        ans[stack.peek()] = i;
        stack.pop();
    }
    stack.push(i);
}
1
2
3
4
5
6
7
8
9
10
11

三、Leetcode 练习

3.1 下一个更大元素 I

下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new ArrayDeque<>();
        int n1 = nums1.length;
        int n2 = nums2.length;
        int [] ans = new int[n1];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = n2 - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
                stack.pop();
            }
        	map.put(nums2[i], stack.isEmpty() ? -1: stack.peek());
        	stack.push(i);
        }

        for (int i = 0; i < n1; i++) {
            int t = map.get(nums1[i]);
            ans[i] = t == -1 ? -1 : nums2[t];
        }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.2 下一个更大元素 II

下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int [] ans = new int[n];
    Arrays.fill(ans, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i <  2 * n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
            ans[stack.peek()] = nums[i % n];
            stack.pop();
        }
        stack.push(i % n);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

四、总结

1. 单调栈有保存具体数据或索引两种做法，具体情况具体分析，两者就是在比较和处理不存在的数据略有所不同，保存索引可以用-1来保持，保存具体数据需要找一个不在范围的数据来替代，总之保存索引更有通用性，推荐保存索引
2. 单调栈遍历有从前往后和从后往前遍历两种，两者略有所不同，以上面找出右边第一个大的值为例，从后往前遍历是找出当前遍历值nums[i] 的右边第一个大的值，而从前往后遍历是找出右边第一个大的值是nums[i]的索引
3. 上述例子仅仅是找出右边第一个大的，如果是找出右边第一个小的，那只要为单调递增栈即可，如果是左边第一个小/大的值，那也只要将遍历方向翻转一下即可

参考

• https://leetcode.cn/problems/next-greater-element-i/
• https://leetcode.cn/problems/next-greater-element-ii/