罗罗编程学习记录
本页内容 展开查看

02.11.2 稀疏表与单调队列栈进阶

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.11 高级数据结构

覆盖范围

  • ST 表稀疏表与 RMQ
  • 单调队列滑动窗口最大值
  • 单调栈每日温度/柱状图/接雨水
  • 三者对比与适用场景

高频题速览

编号 题目 难度 频率
02.11.2-001 ST 表稀疏表构建 进阶 ★★★
02.11.2-002 ST 表 RMQ 查询 进阶 ★★★
02.11.2-003 ST 表 vs 线段树 基础 ★★★
02.11.2-004 单调队列滑动窗口最大值 基础 ★★★★★
02.11.2-005 单调栈每日温度 基础 ★★★★
02.11.2-006 单调栈柱状图最大矩形 进阶 ★★★★
02.11.2-007 单调栈接雨水 进阶 ★★★★
02.11.2-008 三者对比与适用场景 基础 ★★★

02.11.2-001 ST 表稀疏表构建

频率 ★★★ | 难度 进阶

一句话结论

ST 表用 st[j][i] 表示区间 [i, i + 2^j - 1] 的最小值;构建时 st[j][i] = min(st[j-1][i], st[j-1][i + 2^(j-1)]);预处理 O(n log n),查询 O(1)。

概念解释

  • st[j][i]:长度为 2^j 的区间,起点 i。
  • 倍增:长度 2^j 由两个 2^(j-1) 区间合并。
  • 预处理:O(n log n)。

原理流程

  1. st[0][i] = a[i]。
  2. 对 j=1..logn:st[j][i] = min(st[j-1][i], st[j-1][i + 2^(j-1)])。
  3. 空间 O(n log n)。

代码 / 示例

class SparseTable {
    private final int[][] st;
    private final int[] log;
    SparseTable(int[] a) {
        int n = a.length;
        int k = (int)(Math.log(n) / Math.log(2)) + 1;
        st = new int[k][n];
        log = new int[n + 1];
        for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
        for (int i = 0; i < n; i++) st[0][i] = a[i];
        for (int j = 1; j < k; j++)
            for (int i = 0; i + (1 << j) <= n; i++)
                st[j][i] = Math.min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    }
}

常见误区

  • 误区:st[j][i] 表示长度 2^j 但终点写错;正解:区间是 [i, i + 2^j - 1]。
  • 误区:log 数组不预处理;正解:查询时需要 log 快速取整,预处理 log 数组。

追问 / 延伸

  • Q:ST 表支持修改吗? A:不支持,静态区间查询。
  • Q:ST 表支持什么操作? A:最小值、最大值、gcd 等满足幂等性的操作。

02.11.2-002 ST 表 RMQ 查询

频率 ★★★ | 难度 进阶

一句话结论

查询区间 [l, r]:k = log(r-l+1),答案 = min(st[k][l], st[k][r - 2^k + 1]);两个长度 2^k 的区间重叠但覆盖 [l, r],最小值取重叠不影响。

概念解释

  • k = floor(log(r-l+1))。
  • 两个区间:[l, l+2^k-1] 和 [r-2^k+1, r]。
  • 重叠:两个区间有重叠,但最小值幂等,重叠不影响。

原理流程

  1. k = log(r-l+1)。
  2. 返回 min(st[k][l], st[k][r - 2^k + 1])。
  3. O(1) 查询。

代码 / 示例

int query(int l, int r) {
    int k = log[r - l + 1];
    return Math.min(st[k][l], st[k][r - (1 << k) + 1]);
}

常见误区

  • 误区:两个区间不重叠;正解:允许重叠,因为 min 幂等。
  • 误区:k 取 ceil 而不是 floor;正解:k 必须 floor,否则 2^k > r-l+1。

追问 / 延伸

  • Q:为什么允许重叠? A:min 是幂等操作,重叠部分取两次 min 不影响结果。
  • Q:sum 能用 ST 表吗? A:sum 不幂等,重叠会重复计算,不能用。

02.11.2-003 ST 表 vs 线段树

频率 ★★★ | 难度 基础

一句话结论

ST 表预处理 O(n log n),查询 O(1),但不支持修改;线段树预处理 O(n),查询 O(log n),支持修改;静态 RMQ 用 ST 表,动态用线段树。

概念解释

  • ST 表:静态、O(1) 查询、O(n log n) 预处理。
  • 线段树:动态、O(log n) 查询、O(n) 预处理。
  • 选型:不修改用 ST 表,需要修改用线段树。

原理流程

  1. 数组不变、查询多:ST 表。
  2. 数组会修改:线段树。
  3. 查询操作是 min/max/gcd(幂等):ST 表。
  4. 查询操作是 sum:线段树(或树状数组)。

代码 / 图示

特性       ST 表           线段树
预处理     O(n log n)      O(n)
查询       O(1)            O(log n)
修改       不支持          支持
操作类型   min/max/gcd     任意
空间       O(n log n)      O(n)

常见误区

  • 误区:ST 表支持 sum;正解:sum 不幂等,重叠会重复计算。
  • 误区:ST 表支持修改;正解:修改需要重新预处理整个区间。

追问 / 延伸

  • Q:ST 表空间大? A:O(n log n),n=1e6 时约 1e7 个 int,可接受。
  • Q:RMQ 还有什么算法? A:笛卡尔树 + LCA,O(n) 预处理 O(1) 查询,但复杂。

02.11.2-004 单调队列滑动窗口最大值

频率 ★★★★★ | 难度 基础

一句话结论

用双端队列维护单调递减序列(队首最大);新元素入队时从队尾弹出所有比它小的元素;队首过期则弹出;每次滑动窗口最大值 = 队首。

概念解释

  • 单调队列:队首最大,队尾最小。
  • 入队:从队尾弹出比新元素小的,再入队。
  • 过期:队首索引超出窗口范围则弹出。

原理流程

  1. for i in 0..n:
  2. 队首过期(deque.peekFirst() < i-k+1)则弹出。
  3. 从队尾弹出所有 <= a[i] 的元素,入队 i。
  4. 窗口最大值 = a[deque.peekFirst()]。

代码 / 示例

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    java.util.Deque<Integer> deque = new java.util.ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.pollFirst();
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) deque.pollLast();
        deque.offerLast(i);
        if (i >= k - 1) res[i - k + 1] = nums[deque.peekFirst()];
    }
    return res;
}

常见误区

  • 误区:队列存值不存索引;正解:必须存索引,才能判断过期。
  • 误区:弹出条件是 < 而不是 <=;正解:弹出 <= 保证相同值时保留最新的,避免旧值过期时影响。

追问 / 延伸

  • Q:时间复杂度? A:每个元素入队一次出队一次,O(n)。
  • Q:单调队列和单调栈区别? A:队列是滑动窗口(两端操作),栈是栈(一端操作)。

02.11.2-005 单调栈每日温度

频率 ★★★★ | 难度 基础

一句话结论

栈存索引,单调递减;从右往左遍历,弹出所有温度 <= 当前的栈顶索引,答案 = 栈顶索引 - 当前索引;当前索引入栈。

概念解释

  • 单调递减栈:栈顶温度最小。
  • 从右往左:找下一个更高温度。
  • 弹出 <= 当前的:栈顶就是下一个更高温度。

原理流程

  1. for i = n-1 down to 0:
  2. while 栈非空且 temperatures[栈顶] <= temperatures[i],弹出。
  3. res[i] = 栈空 ? 0 : 栈顶 - i。
  4. i 入栈。

代码 / 示例

int[] dailyTemperatures(int[] t) {
    int n = t.length;
    int[] res = new int[n];
    java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && t[stack.peek()] <= t[i]) stack.pop();
        res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
        stack.push(i);
    }
    return res;
}

常见误区

  • 误区:从左往右遍历;正解:从右往左更容易理解,也可以从左往右(找下一个更大元素)。
  • 误区:弹出条件是 < 而不是 <=;正解:弹出 <= 保证栈顶是严格更大。

追问 / 延伸

  • Q:从左往右怎么写? A:for i in 0..n,while 栈非空且 t[栈顶] < t[i],res[栈顶] = i - 栈顶,弹出;i 入栈。
  • Q:时间复杂度? A:每个元素入栈一次出栈一次,O(n)。

02.11.2-006 单调栈柱状图最大矩形

频率 ★★★★ | 难度 进阶

一句话结论

在柱状图末尾加一个高度 0 的哨兵;栈存索引,单调递增;新柱子高度小于栈顶时弹出栈顶,计算以栈顶高度为高的矩形面积 = 高度 * (当前 i - 新栈顶 - 1)。

概念解释

  • 单调递增栈:栈顶高度最小。
  • 弹出时机:当前高度 < 栈顶高度。
  • 宽度:当前 i - 新栈顶 - 1。

原理流程

  1. heights 末尾加 0。
  2. for i in 0..n:
  3. while 栈非空且 heights[栈顶] > heights[i]: h = heights[栈顶],弹出。 w = 栈空 ? i : i - 栈顶 - 1。 area = h * w,更新 maxArea。
  4. i 入栈。

代码 / 示例

int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] h = new int[n + 1];
    System.arraycopy(heights, 0, h, 0, n);
    h[n] = 0;
    java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
    int maxArea = 0;
    for (int i = 0; i <= n; i++) {
        while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
            int height = h[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

常见误区

  • 误区:宽度算成 i - 栈顶;正解:弹出后栈顶是左边界,宽度 = i - 栈顶 - 1(左边界到 i 之间)。
  • 误区:不加哨兵 0;正解:不加哨兵,最后栈里还有元素没计算,需要额外处理。

追问 / 延伸

  • Q:最大矩形面积的宽度怎么理解? A:以弹出的柱子高度为高,向左向右扩展到第一个比它矮的柱子,宽度就是这两个柱子之间的距离。
  • Q:接雨水也能用单调栈吗? A:可以,见下一题。

02.11.2-007 单调栈接雨水

频率 ★★★★ | 难度 进阶

一句话结论

栈存索引,单调递减;新柱子高度大于栈顶时弹出栈顶作为底,计算积水 = (min(左边界, 右边界) - 底) * 宽度;左边界是新栈顶,右边界是当前 i。

概念解释

  • 单调递减栈:栈顶高度最小。
  • 弹出时机:当前高度 > 栈顶高度。
  • 积水:左右边界之间,底以上的部分。

原理流程

  1. for i in 0..n:
  2. while 栈非空且 height[栈顶] < height[i]: bottom = height[栈顶],弹出。 栈空则 break。 left = height[栈顶],right = height[i]。 water = (min(left, right) - bottom) * (i - 栈顶 - 1)。
  3. i 入栈。

代码 / 示例

int trap(int[] height) {
    int n = height.length;
    java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
    int water = 0;
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
            int bottom = height[stack.pop()];
            if (stack.isEmpty()) break;
            int left = height[stack.peek()];
            int w = i - stack.peek() - 1;
            water += (Math.min(left, height[i]) - bottom) * w;
        }
        stack.push(i);
    }
    return water;
}

常见误区

  • 误区:弹出后栈空时不 break;正解:栈空说明没有左边界,不能积水。
  • 误区:宽度算成 i - 弹出索引;正解:宽度 = i - 新栈顶 - 1,因为新栈顶是左边界。

追问 / 延伸

  • Q:接雨水还有什么方法? A:双指针 O(1) 空间,或前缀最大值 O(n) 空间。
  • Q:单调栈和双指针哪个好? A:双指针空间 O(1) 更优,但单调栈思路通用。

02.11.2-008 三者对比与适用场景

频率 ★★★ | 难度 基础

一句话结论

ST 表用于静态区间 min/max/gcd 查询;单调队列用于滑动窗口最大值/最小值;单调栈用于找下一个更大/更小元素、柱状图、接雨水。

概念解释

  • ST 表:静态、幂等操作。
  • 单调队列:滑动窗口、两端操作。
  • 单调栈:找下一个更大/更小、柱状图。

原理流程

  1. 区间查询 min/max,数组不变:ST 表。
  2. 滑动窗口最大值:单调队列。
  3. 找下一个更大元素:单调栈。
  4. 柱状图最大矩形/接雨水:单调栈。

代码 / 图示

结构       操作类型           时间复杂度   适用场景
ST 表      静态区间 min/max   O(n log n) 预处理, O(1) 查询
单调队列   滑动窗口最大/最小   O(n)
单调栈     下一个更大/更小    O(n)

常见误区

  • 误区:单调队列和单调栈混用;正解:队列是两端操作(滑动窗口),栈是一端操作(找下一个更大)。
  • 误区:ST 表支持 sum;正解:sum 不幂等,不能用 ST 表。

追问 / 延伸

  • Q:单调队列能找下一个更大吗? A:可以,但不如单调栈直接。
  • Q:单调栈能做滑动窗口最大值吗? A:不能,单调栈是一端,滑动窗口需要两端操作。

待整理清单

  • [ ] 笛卡尔树与 LCA
  • [ ] 单调栈综合题
  • [ ] ST 表二维扩展