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)。
原理流程
- st[0][i] = a[i]。
- 对 j=1..logn:st[j][i] = min(st[j-1][i], st[j-1][i + 2^(j-1)])。
- 空间 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]。
- 重叠:两个区间有重叠,但最小值幂等,重叠不影响。
原理流程
- k = log(r-l+1)。
- 返回 min(st[k][l], st[k][r - 2^k + 1])。
- 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 表,需要修改用线段树。
原理流程
- 数组不变、查询多:ST 表。
- 数组会修改:线段树。
- 查询操作是 min/max/gcd(幂等):ST 表。
- 查询操作是 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 单调队列滑动窗口最大值
频率 ★★★★★ | 难度 基础
一句话结论
用双端队列维护单调递减序列(队首最大);新元素入队时从队尾弹出所有比它小的元素;队首过期则弹出;每次滑动窗口最大值 = 队首。
概念解释
- 单调队列:队首最大,队尾最小。
- 入队:从队尾弹出比新元素小的,再入队。
- 过期:队首索引超出窗口范围则弹出。
原理流程
- for i in 0..n:
- 队首过期(deque.peekFirst() < i-k+1)则弹出。
- 从队尾弹出所有 <= a[i] 的元素,入队 i。
- 窗口最大值 = 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 单调栈每日温度
频率 ★★★★ | 难度 基础
一句话结论
栈存索引,单调递减;从右往左遍历,弹出所有温度 <= 当前的栈顶索引,答案 = 栈顶索引 - 当前索引;当前索引入栈。
概念解释
- 单调递减栈:栈顶温度最小。
- 从右往左:找下一个更高温度。
- 弹出 <= 当前的:栈顶就是下一个更高温度。
原理流程
- for i = n-1 down to 0:
- while 栈非空且 temperatures[栈顶] <= temperatures[i],弹出。
- res[i] = 栈空 ? 0 : 栈顶 - i。
- 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。
原理流程
- heights 末尾加 0。
- for i in 0..n:
- while 栈非空且 heights[栈顶] > heights[i]: h = heights[栈顶],弹出。 w = 栈空 ? i : i - 栈顶 - 1。 area = h * w,更新 maxArea。
- 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。
概念解释
- 单调递减栈:栈顶高度最小。
- 弹出时机:当前高度 > 栈顶高度。
- 积水:左右边界之间,底以上的部分。
原理流程
- for i in 0..n:
- while 栈非空且 height[栈顶] < height[i]: bottom = height[栈顶],弹出。 栈空则 break。 left = height[栈顶],right = height[i]。 water = (min(left, right) - bottom) * (i - 栈顶 - 1)。
- 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 表:静态、幂等操作。
- 单调队列:滑动窗口、两端操作。
- 单调栈:找下一个更大/更小、柱状图。
原理流程
- 区间查询 min/max,数组不变:ST 表。
- 滑动窗口最大值:单调队列。
- 找下一个更大元素:单调栈。
- 柱状图最大矩形/接雨水:单调栈。
代码 / 图示
结构 操作类型 时间复杂度 适用场景
ST 表 静态区间 min/max O(n log n) 预处理, O(1) 查询
单调队列 滑动窗口最大/最小 O(n)
单调栈 下一个更大/更小 O(n)
常见误区
- 误区:单调队列和单调栈混用;正解:队列是两端操作(滑动窗口),栈是一端操作(找下一个更大)。
- 误区:ST 表支持 sum;正解:sum 不幂等,不能用 ST 表。
追问 / 延伸
- Q:单调队列能找下一个更大吗? A:可以,但不如单调栈直接。
- Q:单调栈能做滑动窗口最大值吗? A:不能,单调栈是一端,滑动窗口需要两端操作。
待整理清单
- [ ] 笛卡尔树与 LCA
- [ ] 单调栈综合题
- [ ] ST 表二维扩展