当前位置：首页 > news >正文

单调栈问题

news 2025/8/5 23:33:14

原理

单调栈的核心原理是：在栈内保持元素的单调性（递增或递减）

单调递增栈：

用于处理“下一个更小的元素”问题。当新元素比栈顶元素小或等于时，直接入栈；否则，一直从栈顶弹出元素，直到栈顶元素小于新元素或栈为空。

单调递减栈：

用于处理“下一个更大的元素”问题。当新元素比栈顶元素大时，一直从栈顶弹出元素，直到栈顶元素大于新元素或栈为空，然后将新元素入栈。

核心代码框架

#include <vector>
#include <stack>
using namespace std;vector<int> nextGreaterElement(vector<int>& nums) {int n = nums.size();vector<int> res(n, -1);  // 默认值为-1，表示没有找到stack<int> stk;          // 用于存储元素索引的单调栈for (int i = 0; i < n; i++) {// 维护栈的单调递减性while (!stk.empty() && nums[stk.top()] < nums[i]) {int idx = stk.top(); // 栈顶元素索引stk.pop();res[idx] = nums[i]; // 找到了下一个更大的元素}stk.push(i); // 入栈当前元素索引}return res;
}

739. 每日温度

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> res(n,0);stack<int>stk;for(int i = 0;i<n;i++){// 递增while(!stk.empty() && temperatures[stk.top()]<temperatures[i]){int index = stk.top(); // 栈顶元素stk.pop();res[index] = i-index;//res[index] = temperatures[i];}stk.push(i);}for(int i = 0;i<n;i++){cout<<res[i]<<endl;}return res;}
};

496.下一个更大元素 I

思路：暴力法

直接足步循环
先找到和 nums1 对应的 nums2 数，找到后，在循环找更大的，找到就退出

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();int m = nums2.size();vector<int> res (n,-1); // -1代表没找到stack<int>stk;for(int i = 0;i<n;i++){int j = 0;while(nums1[i] != nums2[j]){j++;}for(int k = j+1; k<m;k++){if(nums2[k]>nums1[i]){res[i] = nums2[k];break;}}}return res;}
};

思路二：单调栈

我们可以先对 nums2 进行单调栈，找到他每个元素的的下一个更大的数
再根据 nums1 创建数组

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();int m = nums2.size();unordered_map<int, int> nxetnum;vector<int> res (n,-1); // -1代表没找到stack<int>stk;// 遍历 nums2for(int num : nums2){while(!stk.empty()&& stk.top()<num){nxetnum[stk.top()] = num;stk.pop();}stk.push(num);}// 如果没有更大元素，则对应结果为 -1；while(!stk.empty()){nxetnum[stk.top()] = -1;stk.pop();}// 从nums1 中查找对应的；for(int i = 0;i<n;i++){res[i] = nxetnum[nums1[i]];}return res;}
};

503.下一个更大元素II

思路：

因为可以循环，直接将数组进行拼接，这样就破解循环问题了，就如同前面的每日温度问题了

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();vector<int>realnums;// 暴力拼接for(int i = 0; i<2;i++){for(int num:nums){realnums.push_back(num);}}vector<int> res(2*n,-1);stack<int>stk;for(int i = 0;i<realnums.size();i++){while(!stk.empty() && realnums[stk.top()]<realnums[i]){int index = stk.top();stk.pop();res[index] = realnums[i];}stk.push(i);}vector<int>resnum;resnum.insert(resnum.end(),res.begin(),res.begin()+n);return resnum;}
};

代码优化一下：

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();vector<int>realnums(n,-1);stack<int>stk;for(int i = 0 ;i<2*n;i++){int num = nums[i % n];while(!stk.empty() && nums[stk.top()] <num){int index = stk.top();stk.pop();realnums[index]  = num;}if(i<n){stk.push(i);}}return realnums;}
};