企业官网建设流程全解析

引言

前面我们学习了栈和队列的基本操作。今天要讲的是它们的进阶应用——单调栈和单调队列。

普通的栈和队列只负责"存数据"，不关心数据之间的关系。单调栈和单调队列则在存入数据时主动维护元素的单调性——让栈内元素始终保持递增或递减，不满足条件的元素会被弹出丢弃。

这两种结构看似简单，却能以 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; }

三、变体总结

第二部分：经典问题——接雨水

题目：给定[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]，窗口大小 k=3，求每个窗口的最大值。

单调递减队列解法：

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：栈顶弹出后，如果栈空了，说明左边没有更高的墙，当前柱子左边全是洼地，接不住水。

总结

一、核心要点

二、代码框架记忆

单调栈（递减，求下一个更大）： 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)。