栈、队列 & 单调结构

概览

栈和队列的本质是约束访问顺序：栈只能操作顶部（LIFO），队列只能操作两端（FIFO）。单调栈/单调双端队列在此基础上额外维护一个单调性不变量——新元素进入时弹出破坏单调性的旧元素，保证每个元素最多入栈出栈各一次，从而将区间极值问题从 O(n²) 降到 O(n)。

四种结构速查

单调栈核心思路

维护不变量：栈中元素从栈底到栈顶单调（递增或递减）。当新元素 x 进入时，弹出所有不满足单调性的栈顶，弹出时即可确定被弹元素的「答案」（下一个更大/更小元素）。每个元素只进出一次，整体 O(n)。

⚠️ pop() 无返回值

C++ 的 stack::pop() / queue::pop() 不返回值！读值必须先 top()/front()，再 pop()。

// ❌ Wrong — pop() returns void
int x = st.pop();

// ✅ Correct
int x = st.top();
st.pop();

复杂度

栈：括号匹配

括号匹配是栈最经典的应用：遇到左括号压栈，遇到右括号弹栈检查是否配对，最后栈空则合法。

核心思想

左括号入栈；右括号时若栈空或栈顶不匹配，则非法；匹配则弹栈。扫描完毕后栈若非空（有未配对的左括号）也非法。

步骤

1. 遍历字符串每个字符 c
2. 若 c 是左括号（'(' / '[' / '{'），压栈
3. 若 c 是右括号，判断栈是否为空（为空则非法）
4. 弹出栈顶，检查是否与 c 配对，不配对则非法
5. 遍历结束，栈空则合法，否则非法

C++ 实现

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top(); st.pop(); // read THEN pop
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return st.empty(); // unmatched openings → false
}

栈的其他经典用途

常见错误

单调递减栈：下一个更大元素

栈中元素从栈底到栈顶单调递减（按值）。当新元素比栈顶大时，栈顶元素找到了它的「下一个更大元素」，弹出并记录答案。

核心思想

栈存下标，栈中对应的值从底到顶单调递减。遍历数组时：若 nums[i] > nums[st.top()]，则 st.top() 的「下一个更大元素」就是 nums[i]，反复弹出直到栈空或栈顶 >= nums[i]，然后把 i 入栈。最终还在栈里的元素答案为 -1。

步骤

1. 初始化 ans 数组全为 -1，stack<int> st 存下标
2. 从左到右遍历 i = 0..n-1
3. while (!st.empty() && nums[st.top()] < nums[i])：ans[st.top()] = nums[i]；st.pop()
4. st.push(i)
5. 遍历结束，栈中剩余下标对应答案保持 -1

C++ 实现

// Next Greater Element: for each nums[i], find the first element to its
// right that is strictly greater. Returns -1 if none exists.
vector<int> nextGreater(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1);
    stack<int> st; // stores indices; values decrease from bottom to top
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            ans[st.top()] = nums[i]; // st.top() found its answer
            st.pop();
        }
        st.push(i);
    }
    // remaining indices stay -1 (no greater element to the right)
    return ans;
}

变体

常见错误

单调递增栈：柱状图最大矩形

栈中元素从栈底到栈顶单调递增（按高度）。当新柱比栈顶矮时，弹出栈顶并计算以该高度为上界的最大矩形面积。

核心思想

对于被弹出的柱子 heights[top]：它的左边界是新栈顶（因为栈中元素单调递增，栈顶左边的柱必然更矮），右边界是当前 i。面积 = heights[top] × (i - newTop - 1)。在数组末尾追加哨兵高度 0，确保所有元素最终都被弹出处理。

步骤

1. 在 heights 末尾追加 0（哨兵），使最后所有元素都被弹出
2. 遍历 i = 0..n（含哨兵）
3. while (!st.empty() && heights[st.top()] > heights[i])：
4. height = heights[st.top()]; st.pop()
5. width = st.empty() ? i : i - st.top() - 1
6. maxArea = max(maxArea, height * width)
7. st.push(i)

C++ 实现

// Largest Rectangle in Histogram using monotonic increasing stack + sentinel
int largestRectangle(vector<int>& heights) {
    heights.push_back(0); // sentinel flushes all remaining bars
    int n = heights.size(), maxArea = 0;
    stack<int> st; // indices; corresponding heights increase bottom→top
    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[st.top()] > heights[i]) {
            int h = heights[st.top()]; st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, h * w);
        }
        st.push(i);
    }
    heights.pop_back(); // restore original array
    return maxArea;
}

常见错误

单调双端队列：滑动窗口最大值

用双端队列（deque）维护单调递减序列的下标：队首是当前窗口最大值的下标；队尾维护单调性，新元素进入时弹出队尾所有更小的元素。

核心思想

deque 中存下标，对应值从队首到队尾单调递减。新元素 nums[i] 入队前，从队尾弹出所有 < nums[i] 的元素（它们永远不会是窗口最大值）；同时若队首下标已不在窗口内（< i-k+1），从队首弹出。窗口形成后（i >= k-1），队首即为当前窗口最大值下标。

步骤

1. deque<int> dq 存下标，从队首到队尾对应值单调递减
2. 遍历 i = 0..n-1
3. 队首过期：while (!dq.empty() && dq.front() < i-k+1) dq.pop_front()
4. 维护单调性：while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back()
5. dq.push_back(i)
6. 窗口就绪（i >= k-1）：ans.push_back(nums[dq.front()])

C++ 实现

// Sliding Window Maximum using monotonic decreasing deque
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // stores indices; corresponding values decrease front→back
    vector<int> ans;
    for (int i = 0; i < (int)nums.size(); i++) {
        // 1. Remove expired front (outside window)
        while (!dq.empty() && dq.front() < i - k + 1)
            dq.pop_front();
        // 2. Maintain decreasing order from back
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();
        dq.push_back(i);
        // 3. Window is full: record maximum
        if (i >= k - 1) ans.push_back(nums[dq.front()]);
    }
    return ans;
}

变体

常见错误

LeetCode 题型

按结构分类的高频栈/队列题目。

栈基础

单调递减栈（求更大元素）

单调递增栈（求更小元素/面积）

单调双端队列