引言前面我们学习了栈和队列的基本操作。今天要讲的是它们的进阶应用——单调栈和单调队列。普通的栈和队列只负责存数据不关心数据之间的关系。单调栈和单调队列则在存入数据时主动维护元素的单调性——让栈内元素始终保持递增或递减不满足条件的元素会被弹出丢弃。这两种结构看似简单却能以 O(n) 的时间复杂度解决一系列经典问题接雨水、柱状图中最大矩形、滑动窗口最大值、每日温度……都是面试中的常客。第一部分单调栈一、什么是单调栈单调栈 栈 元素单调性。从栈底到栈顶元素严格递增或递减。// 单调递减栈的核心逻辑以找下一个更大元素为例 for (int i 0; i n; i) { // 当前元素 栈顶元素 → 栈顶元素找到了下一个更大值 while (!empty() arr[i] arr[top()]) { int idx pop(); // 栈顶元素的下标 result[idx] arr[i]; // arr[i] 就是它的下一个更大值 } push(i); // 当前元素入栈存下标 }二、经典问题下一个更大元素题目给定数组[2, 1, 3, 5, 4]求每个元素的下一个更大元素右边第一个比自己大的数。没有则返回 -1。#include stdio.h #include stdlib.h int* nextGreaterElement(int* arr, int n) { int* result (int*)malloc(sizeof(int) * n); int* stack (int*)malloc(sizeof(int) * n); int top -1; for (int i 0; i n; i) { // 当前元素比栈顶大 → 出栈记录结果 while (top ! -1 arr[i] arr[stack[top]]) { result[stack[top]] arr[i]; top--; } // 当前元素入栈存下标 stack[top] i; } // 栈中剩余元素 → 没有下一个更大值 while (top ! -1) { result[stack[top]] -1; top--; } free(stack); return result; }三、变体总结问题栈类型出栈条件下一个更大元素递减栈arr[i] arr[top]下一个更小元素递增栈arr[i] arr[top]上一个更大元素递减栈倒序遍历上一个更小元素递增栈倒序遍历第二部分经典问题——接雨水题目给定[0,1,0,2,1,0,1,3,2,1,2,1]计算能接多少雨水。int trap(int* height, int n) { int* stack (int*)malloc(sizeof(int) * n); int top -1; int water 0; for (int i 0; i n; i) { while (top ! -1 height[i] height[stack[top]]) { int bottom stack[top--]; // 凹槽底部 if (top -1) break; // 左边没有墙接不住水 int left stack[top]; // 左墙 int w i - left - 1; // 宽度 int h (height[left] height[i] ? height[left] : height[i]) - height[bottom]; water w * h; } stack[top] i; } free(stack); return water; }核心思路当前柱子比栈顶高时栈顶元素就是凹槽底部栈顶下面的是左墙当前柱子是右墙。第三部分单调队列一、什么是单调队列单调队列 双端队列 元素单调性。从队头到队尾元素严格递增或递减。单调队列的核心操作队尾入队时把前面比它小或大的元素都踢出去。// 单调递减队列队头最大 typedef struct { int* data; int front, rear; } MonoQueue; // 队尾入队把前面所有比 val 小的都踢出去 void push_back(MonoQueue* q, int val) { while (q-front q-rear q-data[q-rear - 1] val) { q-rear--; // 踢出去 } q-data[q-rear] val; }二、经典问题滑动窗口最大值题目给定数组[1, 3, -1, -3, 5, 3, 6, 7]窗口大小 k3求每个窗口的最大值。单调递减队列解法int* maxSlidingWindow(int* nums, int n, int k, int* returnSize) { *returnSize n - k 1; int* result (int*)malloc(sizeof(int) * (*returnSize)); int* deque (int*)malloc(sizeof(int) * n); // 存下标 int front 0, rear 0; for (int i 0; i n; i) { // ① 队头滑出窗口 → 出队 if (front rear deque[front] i - k) { front; } // ② 队尾入队踢出所有比当前值小的 while (front rear nums[deque[rear - 1]] nums[i]) { rear--; } deque[rear] i; // ③ 窗口形成后队头就是最大值 if (i k - 1) { result[i - k 1] nums[deque[front]]; } } free(deque); return result; }第四部分单调栈 vs 单调队列对比项单调栈单调队列数据结构栈一端进出双端队列两端操作维护单调性入栈时踢出队尾入队时踢出元素过期不涉及队头可能滑出窗口适用场景找下一个更大/更小滑动窗口最值典型问题接雨水、柱状图最大矩形滑动窗口最大值第五部分面试题1. Q单调栈和单调队列的核心区别A单调栈只在栈顶操作适合找最近/下一个更大元素类问题。单调队列需要维护队头和队尾适合滑动窗口最值类问题队头会过期出队。2. Q为什么单调栈通常存下标而不是值A存下标既能拿到值又能计算距离如宽度。接雨水中需要知道两个柱子之间的距离下一个更大元素中需要知道结果放到哪个位置。3. Q接雨水问题中什么时候接不住水A栈顶弹出后如果栈空了说明左边没有更高的墙当前柱子左边全是洼地接不住水。总结一、核心要点要点内容单调栈入栈时把不配留在栈里的弹出去维护单调性单调队列队尾入队时踢出队头过期时移除维护单调性单调递减栈求下一个更大元素、接雨水单调递增栈求下一个更小元素单调递减队列滑动窗口最大值时间复杂度每个元素最多入一次、出一次 →O(n)二、代码框架记忆单调栈递减求下一个更大 for i in 0..n-1: while 栈非空 arr[i] arr[栈顶]: result[栈顶] arr[i]; 出栈 入栈(i) 栈剩余 → result -1 单调队列递减滑动窗口最大值 for i in 0..n-1: if 队头滑出窗口: 队头出队 while 队非空 arr[i] arr[队尾]: 队尾出队 队尾入队(i) if i k-1: result arr[队头]三、一句话记忆单调栈和单调队列的核心是不配的踢出去。单调栈在一端操作解决下一个更大/更小元素和接雨水单调队列在两端操作解决滑动窗口最值。每个元素最多进出一次复杂度 O(n)。
单调栈与单调队列：高效解决经典算法问题
引言前面我们学习了栈和队列的基本操作。今天要讲的是它们的进阶应用——单调栈和单调队列。普通的栈和队列只负责存数据不关心数据之间的关系。单调栈和单调队列则在存入数据时主动维护元素的单调性——让栈内元素始终保持递增或递减不满足条件的元素会被弹出丢弃。这两种结构看似简单却能以 O(n) 的时间复杂度解决一系列经典问题接雨水、柱状图中最大矩形、滑动窗口最大值、每日温度……都是面试中的常客。第一部分单调栈一、什么是单调栈单调栈 栈 元素单调性。从栈底到栈顶元素严格递增或递减。// 单调递减栈的核心逻辑以找下一个更大元素为例 for (int i 0; i n; i) { // 当前元素 栈顶元素 → 栈顶元素找到了下一个更大值 while (!empty() arr[i] arr[top()]) { int idx pop(); // 栈顶元素的下标 result[idx] arr[i]; // arr[i] 就是它的下一个更大值 } push(i); // 当前元素入栈存下标 }二、经典问题下一个更大元素题目给定数组[2, 1, 3, 5, 4]求每个元素的下一个更大元素右边第一个比自己大的数。没有则返回 -1。#include stdio.h #include stdlib.h int* nextGreaterElement(int* arr, int n) { int* result (int*)malloc(sizeof(int) * n); int* stack (int*)malloc(sizeof(int) * n); int top -1; for (int i 0; i n; i) { // 当前元素比栈顶大 → 出栈记录结果 while (top ! -1 arr[i] arr[stack[top]]) { result[stack[top]] arr[i]; top--; } // 当前元素入栈存下标 stack[top] i; } // 栈中剩余元素 → 没有下一个更大值 while (top ! -1) { result[stack[top]] -1; top--; } free(stack); return result; }三、变体总结问题栈类型出栈条件下一个更大元素递减栈arr[i] arr[top]下一个更小元素递增栈arr[i] arr[top]上一个更大元素递减栈倒序遍历上一个更小元素递增栈倒序遍历第二部分经典问题——接雨水题目给定[0,1,0,2,1,0,1,3,2,1,2,1]计算能接多少雨水。int trap(int* height, int n) { int* stack (int*)malloc(sizeof(int) * n); int top -1; int water 0; for (int i 0; i n; i) { while (top ! -1 height[i] height[stack[top]]) { int bottom stack[top--]; // 凹槽底部 if (top -1) break; // 左边没有墙接不住水 int left stack[top]; // 左墙 int w i - left - 1; // 宽度 int h (height[left] height[i] ? height[left] : height[i]) - height[bottom]; water w * h; } stack[top] i; } free(stack); return water; }核心思路当前柱子比栈顶高时栈顶元素就是凹槽底部栈顶下面的是左墙当前柱子是右墙。第三部分单调队列一、什么是单调队列单调队列 双端队列 元素单调性。从队头到队尾元素严格递增或递减。单调队列的核心操作队尾入队时把前面比它小或大的元素都踢出去。// 单调递减队列队头最大 typedef struct { int* data; int front, rear; } MonoQueue; // 队尾入队把前面所有比 val 小的都踢出去 void push_back(MonoQueue* q, int val) { while (q-front q-rear q-data[q-rear - 1] val) { q-rear--; // 踢出去 } q-data[q-rear] val; }二、经典问题滑动窗口最大值题目给定数组[1, 3, -1, -3, 5, 3, 6, 7]窗口大小 k3求每个窗口的最大值。单调递减队列解法int* maxSlidingWindow(int* nums, int n, int k, int* returnSize) { *returnSize n - k 1; int* result (int*)malloc(sizeof(int) * (*returnSize)); int* deque (int*)malloc(sizeof(int) * n); // 存下标 int front 0, rear 0; for (int i 0; i n; i) { // ① 队头滑出窗口 → 出队 if (front rear deque[front] i - k) { front; } // ② 队尾入队踢出所有比当前值小的 while (front rear nums[deque[rear - 1]] nums[i]) { rear--; } deque[rear] i; // ③ 窗口形成后队头就是最大值 if (i k - 1) { result[i - k 1] nums[deque[front]]; } } free(deque); return result; }第四部分单调栈 vs 单调队列对比项单调栈单调队列数据结构栈一端进出双端队列两端操作维护单调性入栈时踢出队尾入队时踢出元素过期不涉及队头可能滑出窗口适用场景找下一个更大/更小滑动窗口最值典型问题接雨水、柱状图最大矩形滑动窗口最大值第五部分面试题1. Q单调栈和单调队列的核心区别A单调栈只在栈顶操作适合找最近/下一个更大元素类问题。单调队列需要维护队头和队尾适合滑动窗口最值类问题队头会过期出队。2. Q为什么单调栈通常存下标而不是值A存下标既能拿到值又能计算距离如宽度。接雨水中需要知道两个柱子之间的距离下一个更大元素中需要知道结果放到哪个位置。3. Q接雨水问题中什么时候接不住水A栈顶弹出后如果栈空了说明左边没有更高的墙当前柱子左边全是洼地接不住水。总结一、核心要点要点内容单调栈入栈时把不配留在栈里的弹出去维护单调性单调队列队尾入队时踢出队头过期时移除维护单调性单调递减栈求下一个更大元素、接雨水单调递增栈求下一个更小元素单调递减队列滑动窗口最大值时间复杂度每个元素最多入一次、出一次 →O(n)二、代码框架记忆单调栈递减求下一个更大 for i in 0..n-1: while 栈非空 arr[i] arr[栈顶]: result[栈顶] arr[i]; 出栈 入栈(i) 栈剩余 → result -1 单调队列递减滑动窗口最大值 for i in 0..n-1: if 队头滑出窗口: 队头出队 while 队非空 arr[i] arr[队尾]: 队尾出队 队尾入队(i) if i k-1: result arr[队头]三、一句话记忆单调栈和单调队列的核心是不配的踢出去。单调栈在一端操作解决下一个更大/更小元素和接雨水单调队列在两端操作解决滑动窗口最值。每个元素最多进出一次复杂度 O(n)。
