数据结构 学习 栈 2025年6月14日 11点09分

单调栈

单调栈通过维护数据的单调性，将原本O(n²)的暴力解法优化到O(n)，是解决一系列区间极值问题的利器。掌握单调栈的关键在于理解问题本质并选择合适的单调性方向。

使用技巧

1. 确定单调性：根据问题需求选择递增栈还是递减栈

   • 找下一个更大元素 → 单调递减栈

   • 找下一个更小元素 → 单调递增栈

2. 存储内容：根据问题决定栈内存储元素值还是索引

   • 需要计算宽度 → 存储索引

   • 只需要比较值 → 存储值

3. 边界处理：考虑数组边界情况，可添加哨兵元素简化逻辑

4. 多步操作：有时需要先从左到右扫描，再从右到左扫描

基本概念

1. 单调栈特性

• 单调递增栈：栈内元素从栈底到栈顶保持递增顺序

• 单调递减栈：栈内元素从栈底到栈顶保持递减顺序

2. 常见应用场景

• 寻找下一个更大/更小元素

• 计算柱状图中的最大矩形

• 解决接雨水问题

• 股票跨度问题

 算法实现

//单调递增栈

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st; // 存储的是元素下标
    
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            res[st.top()] = nums[i]; // 当前元素是栈顶元素的下一个更大元素
            st.pop();
        }
        st.push(i);
    }
    return res;
}

//单调递减栈

vector<int> nextSmallerElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;
    
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] > nums[i]) {
            res[st.top()] = nums[i]; // 当前元素是栈顶元素的下一个更小元素
            st.pop();
        }
        st.push(i);
    }
    return res;
}

经典应用

//下一个更大元素  (LeetCode 496)
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    stack<int> st;
    unordered_map<int, int> nextGreater;
    
    for (int num : nums2) {
        while (!st.empty() && st.top() < num) {
            nextGreater[st.top()] = num;
            st.pop();
        }
        st.push(num);
    }
    
    vector<int> res;
    for (int num : nums1) {
        res.push_back(nextGreater.count(num) ? nextGreater[num] : -1);
    }
    return res;
}

//柱状图中的最大矩形 (LeetCode 84)

int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    heights.push_back(0); // 添加哨兵
    int maxArea = 0;
    
    for (int i = 0; i < heights.size(); 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);
    }
    
    return maxArea;
}

//接雨水 (LeetCode 42)

int trap(vector<int>& height) {
    stack<int> st;
    int water = 0;
    
    for (int i = 0; i < height.size(); i++) {
        while (!st.empty() && height[st.top()] < height[i]) {
            int bottom = height[st.top()];
            st.pop();
            if (st.empty()) break;
            int left = st.top();
            int h = min(height[left], height[i]) - bottom;
            int w = i - left - 1;
            water += h * w;
        }
        st.push(i);
    }
    
    return water;
}

//股票跨度问题 (LeetCode 901)

class StockSpanner {
    stack<pair<int, int>> st; // {price, span}
    
public:
    StockSpanner() {}
    
    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }
        st.push({price, span});
        return span;
    }
};

//每日温度 (LeetCode 739)
vector<int> dailyTemperatures(vector<int>& T) {
    int n = T.size();
    vector<int> res(n, 0);
    stack<int> st;
    
    for (int i = 0; i < n; i++) {
        while (!st.empty() && T[st.top()] < T[i]) {
            res[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    
    return res;
}