接雨水

单调栈模版

#include <vector>
#include <stack>
using namespace std;

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);  // 初始化结果数组
    stack<int> st;              // 栈中存储索引
    
    for (int i = 0; i < n; i++) {
        // 维护单调递减栈（找下一个更大元素）
        while (!st.empty() && nums[i] > nums[st.top()]) {
            int idx = st.top();
            st.pop();
            result[idx] = nums[i];  // 当前元素是栈顶元素的下一个更大元素
        }
        st.push(i);
    }
    
    // 栈中剩余元素对应的结果保持为 -1
    return result;
}

#include <vector>
#include <stack>
using namespace std;

class MonotonicStack {
public:
    // 1. 下一个更大元素（右侧第一个更大）
    static vector<int> nextGreater(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[i] > nums[st.top()]) {
                res[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
    
    // 2. 下一个更小元素（右侧第一个更小）
    static vector<int> nextSmaller(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[i] < nums[st.top()]) {
                res[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
    
    // 3. 上一个更大元素（左侧第一个更大）
    static vector<int> previousGreater(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> st; // 单调递减栈
        
        // 逆序遍历找左侧
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && nums[i] > nums[st.top()]) {
                res[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
    
    // 4. 上一个更小元素（左侧第一个更小）
    static vector<int> previousSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> st; // 单调递增栈
        
        // 逆序遍历找左侧
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && nums[i] < nums[st.top()]) {
                res[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};

接雨水

int trap(vector<int> &height) {
    size_t n = height.size();

    int ans = 0;
    stack<int> s;
    for (int i = 0; i < n; ++i) {
      while (!s.empty() && height[i] > height[s.top()]) {
        int bottom_h = height[s.top()];
        s.pop();
        if (s.empty()) break;
        int h = min(height[i], height[s.top()]) - bottom_h;
        int area = (i - s.top() - 1) * h;
        ans += area;
      }
      s.push(i);
    }
    return ans;
  }