数据结构 学习 栈 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;
}