数据结构 学习 栈 2025年6月14日 11点09分
单调栈
单调栈通过维护数据的单调性，将原本O(n²)的暴力解法优化到O(n)，是解决一系列区间极值问题的利器。掌握单调栈的关键在于理解问题本质并选择合适的单调性方向。
使用技巧
确定单调性：根据问题需求选择递增栈还是递减栈
找下一个更大元素 → 单调递减栈
找下一个更小元素 → 单调递增栈
存储内容：根据问题决定栈内存储元素值还是索引
需要计算宽度 → 存储索引
只需要比较值 → 存储值
边界处理：考虑数组边界情况，可添加哨兵元素简化逻辑
多步操作：有时需要先从左到右扫描，再从右到左扫描
基本概念
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;
}