单调栈 | 单调队列

单调栈

解决问题

某位置之后（之前）的第一个大于（小于）自身的元素是谁

时间复杂度

$O(n)$

操作模板

1
2
3
4
5
6
7
8
9
public something solve(int[] a) {
    for (int i = 0; i < a.length; i++) {
        while (!d.isEmpty() && a[i] ? a[d.peek()] 这里的偏序符号(?)取决于是递增(<)还是递减(>)栈) {
            // do something 求和 or 赋值 or 做出自己的处理
        }
        d.push(i);
    }
    return something
}

记忆方式

  1. 下一个更大 $\to$ 递减
  2. 下一个更小 $\to$ 递增

例题1

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

分析：

下一个，更高，因此是单调栈解决的问题，并且是递减栈，如果没有找到下一个，则用0替代，初始化全为0，因此不需要特判，当没有结果的时候不会做处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    Deque<Integer> d = new ArrayDeque<>();
    public int[] dailyTemperatures(int[] a) {
        int n = a.length;
        int[] res = new int[n];
        // 带入修改核心计算结果部分
        for (int i = 0; i < n; i++) {
            while (!d.isEmpty() && a[i] > a[d.peek()]) {
                int t = d.pop();
                res[t] = i - t; // 原题要求的是 几天后 因此做差
            }
            d.push(i);
        }
        return res;
    }
}

例题2

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

每一层是上一层在高度上的累计，然后同一层之内，可以用柱状图中最大矩形来求解，先求列方向的连续的1的个数的前缀和，然后在每一层上求最大矩形就行

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
class Solution {
    private int calc(int[] a) {
        int n = a.length, res = 0;
        int[] b = new int[n + 2];
        System.arraycopy(a, 0, b, 1, n);
        Deque<Integer> d = new ArrayDeque<>();
        // 代入模板，应该是第一个小于当前位置的值，因此是递增栈，这样两侧都是小于自身的，那么以自身为高度的矩形面积就可以通过当前位置和前一个位置求出
        for (int i = 0; i < n + 2; i++) {
            while (!d.isEmpty() && b[i] < b[d.peek()]) {
                int j = d.pop();
                res = Math.max(res, (i - d.peek() - 1) * b[j]);
            }
            d.push(i);
        }
        return res;
    }
    public int maximalRectangle(char[][] a) {
        int n = a.length, m = a[0].length, res = 0;
        int[][] f = new int[n][m];
        for (int j = 0; j < m; j++) f[0][j] = a[0][j] - '0';
        for (int j = 0; j < m; j++) {
            for (int i = 1; i < n; i++) {
                if (a[i][j] == '1') f[i][j] = f[i - 1][j] + (a[i][j] - '0');
            }
        }
        for (int[] x : f) res = Math.max(res, calc(x));
        return res;
    }
}

单调队列

解决问题

滑动窗口的最大（最小）值

操作模板

1
2
3
4
5
6
7
8
9
public void solve(int[] a) {
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < a.length; i++) {
        if (!q.isEmpty() && i - q.peekFirst() >= m) q.pollFirst();
        while (!q.isEmpty() && a[i] > a[q.peekLast()]) q.pollLast();  // 这里的出队条件取决于递减还是递增，如果递减求最大，那么就是大于，否则小于
        q.offer(i);
        if (i >= m - 1) System.out.println(a[q.peekFirst()]);
    }
}

记忆方式

  1. 最小值 $\to$ 单调递增
  2. 最大值 $\to$ 单调递减

例题

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] maxSlidingWindow(int[] a, int m) {
        int n = a.length, p = 0;
        int[] res = new int[n - m + 1];
        // 直接贴上来就行，刚好是符合我们要求的
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < a.length; i++) {
            if (!q.isEmpty() && i - q.peekFirst() >= m) q.pollFirst();
            while (!q.isEmpty() && a[i] > a[q.peekLast()]) q.pollLast();
            q.offer(i);
            if (i >= m - 1) res[p++] = a[q.peekFirst()];
        }
        return res;
    }
}