栈CSP-J

💡 核心思想

栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除。在竞赛中，栈常用于括号匹配、表达式求值、单调栈（求下一个更大/更小元素）等问题。C++ STL 的 stack 或 vector 都可以实现。

🎯 直觉理解

undefined

📝 算法流程

1. 基本操作：push, pop, top, empty
2. 单调栈：维护单调性，不满足时弹出
3. 应用：括号匹配、表达式求值、单调栈

$$\text{单调栈每个元素最多入栈出栈各一次：} O(n)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 单调栈：求每个元素右边第一个比它大的元素
int main() {
    int n; cin >> n;
    vector<int> a(n), ans(n, 0);
    for (auto& x : a) cin >> x;
    stack<int> stk; // 存下标
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && a[stk.top()] < a[i]) {
            ans[stk.top()] = i + 1; // 1-based 位置
            stk.pop();
        }
        stk.push(i);
    }
    for (int x : ans) cout << x << " ";
    return 0;
}

⚠️ 常见坑点

📚 相关题目