外网代理服务器网站快速推广

单调栈

单调栈通过维护数据的单调性，将原本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;
}