做国外网站要注意什么,济南软件公司排名,网站做网站反向代理违法,梁定然网页设计教程原理
单调栈的核心原理是#xff1a;在栈内保持元素的单调性#xff08;递增或递减#xff09;
单调递增栈#xff1a; 用于处理“下一个更小的元素”问题。当新元素比栈顶元素小或等于时#xff0c;直接入栈#xff1b;否则#xff0c;一直从栈顶弹出元素#xff0c…原理
单调栈的核心原理是在栈内保持元素的单调性递增或递减
单调递增栈 用于处理“下一个更小的元素”问题。当新元素比栈顶元素小或等于时直接入栈否则一直从栈顶弹出元素直到栈顶元素小于新元素或栈为空。 单调递减栈 用于处理“下一个更大的元素”问题。当新元素比栈顶元素大时一直从栈顶弹出元素直到栈顶元素大于新元素或栈为空然后将新元素入栈。 核心代码框架
#include vector
#include stack
using namespace std;vectorint nextGreaterElement(vectorint nums) {int n nums.size();vectorint res(n, -1); // 默认值为-1表示没有找到stackint 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:vectorint dailyTemperatures(vectorint temperatures) {int n temperatures.size();vectorint res(n,0);stackintstk;for(int i 0;in;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;in;i){coutres[i]endl;}return res;}
};496.下一个更大元素 I 思路暴力法 直接足步循环 先找到和 nums1 对应的 nums2 数找到后在循环找更大的找到就退出 class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {int n nums1.size();int m nums2.size();vectorint res (n,-1); // -1代表没找到stackintstk;for(int i 0;in;i){int j 0;while(nums1[i] ! nums2[j]){j;}for(int k j1; km;k){if(nums2[k]nums1[i]){res[i] nums2[k];break;}}}return res;}
};思路二单调栈 我们可以先对 nums2 进行单调栈找到他每个元素的的下一个更大的数 再根据 nums1 创建数组 class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {int n nums1.size();int m nums2.size();unordered_mapint, int nxetnum;vectorint res (n,-1); // -1代表没找到stackintstk;// 遍历 nums2for(int num : nums2){while(!stk.empty() stk.top()num){nxetnum[stk.top()] num;stk.pop();}stk.push(num);}// 如果没有更大元素则对应结果为 -1while(!stk.empty()){nxetnum[stk.top()] -1;stk.pop();}// 从nums1 中查找对应的for(int i 0;in;i){res[i] nxetnum[nums1[i]];}return res;}
};503.下一个更大元素II 思路 因为可以循环直接将数组进行拼接这样就破解循环问题了就如同前面的每日温度问题了 class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int n nums.size();vectorintrealnums;// 暴力拼接for(int i 0; i2;i){for(int num:nums){realnums.push_back(num);}}vectorint res(2*n,-1);stackintstk;for(int i 0;irealnums.size();i){while(!stk.empty() realnums[stk.top()]realnums[i]){int index stk.top();stk.pop();res[index] realnums[i];}stk.push(i);}vectorintresnum;resnum.insert(resnum.end(),res.begin(),res.begin()n);return resnum;}
};代码优化一下
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int n nums.size();vectorintrealnums(n,-1);stackintstk;for(int i 0 ;i2*n;i){int num nums[i % n];while(!stk.empty() nums[stk.top()] num){int index stk.top();stk.pop();realnums[index] num;}if(in){stk.push(i);}}return realnums;}
};
