单调栈CSP-S

💡 核心思想

单调栈是一种特殊的栈，栈内元素始终保持单调递增或单调递减。它的核心应用是：对于每个元素，快速找到其左边/右边第一个比它大（或小）的元素。通过维护单调性，每个元素最多入栈出栈一次，达到 O(n) 的时间复杂度。

🎯 直觉理解

想象一群人排队，每个人只能看到前面比自己高的人（被挡住了）。单调栈就像一个"身高递增的队列"：新来的人如果比队尾矮，就站在队尾后面；如果比队尾高，就把前面所有比自己矮的人都"挤出去"——被挤出去的人终于找到了第一个比自己高的人（就是新来的这个人）。

📝 算法流程

1. 初始化一个空栈（栈中存储元素的值或下标）
2. 从左到右遍历每个元素：
3. 当栈非空且当前元素 >= 栈顶元素时，栈顶元素出栈（栈顶找到了右边第一个更大的元素）
4. 当前元素入栈
5. 如果需要找左边第一个更小的元素，则当前元素入栈前的栈顶就是答案
6. 每个元素最多入栈出栈一次，总复杂度 O(n)

$$\text{对于每个 }a_i,\text{ 找右边第一个 }a_j > a_i \text{（其中 }j > i\text{）} Rightarrow O(n)\text{ 用单调栈}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 单调栈：找每个元素右边第一个更大的元素的下标
vector nextGreaterElement(vector& a) {
    int n = a.size();
    vector res(n, -1); // -1 表示不存在
    stack st; // 存下标，保持栈内元素值单调递减
    
    for (int i = 0; i < n; i++) {
        // 当前元素 a[i] 比栈顶大，说明栈顶找到了右边第一个更大的
        while (!st.empty() && a[i] > a[st.top()]) {
            res[st.top()] = i; // 右边第一个更大的是 a[i]
            st.pop();
        }
        st.push(i);
    }
    // 栈中剩余元素的右边没有更大的
    return res;
}

// 单调栈求最大矩形面积（直方图）
int largestRectangleArea(vector& heights) {
    int n = heights.size();
    stack st;
    int maxArea = 0;
    
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i]; // 末尾补 0 确保栈清空
        while (!st.empty() && h < heights[st.top()]) {
            int height = heights[st.top()]; st.pop();
            int width = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        st.push(i);
    }
    return maxArea;
}

int main() {
    vector a = {2, 1, 2, 4, 3};
    auto res = nextGreaterElement(a);
    for (int x : res) cout << x << " "; // 3 -1 3 -1 -1
    cout << endl;
    
    vector h = {2, 1, 5, 6, 2, 3};
    cout << largestRectangleArea(h) << endl; // 10
    return 0;
}

⚠️ 常见坑点

📚 相关题目