笔记:代码随想录算法训练营day48:739. 每日温度\496.下一个更大元素 I\503.下一个更大元素II

学习资料:代码随想录

单调栈适合找左边或右边比当前大或小的元素

739. 每日温度

力扣题目链接

大致意思为用栈存储当前值以及比当前的小的值,但后遇到比当前值大的值的时候再计算

非常巧妙的是,最后需要等于0的时候,正好后面没有比当下大的数的那个数的位置的result保留为0,不用处理

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> st;vector<int> result(temperatures.size(),0);st.push(0);for(int i=1;i<temperatures.size();i++){if(temperatures[i]==temperatures[st.top()]){st.push(i);}else if(temperatures[i]<temperatures[st.top()]){st.push(i);}else{while(!st.empty()&&temperatures[i]>temperatures[st.top()]){   //!st.empty()是必要的,因为访问不到就会报错result[st.top()]=i-st.top();st.pop();}st.push(i);    //先把比i小的都算完再pushi}}return result;}
};

不难发现,<的情况和=的情况可以一并处理

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> st;vector<int> result(temperatures.size(),0);st.push(0);for(int i=1;i<temperatures.size();i++){while(!st.empty()&&temperatures[i]>temperatures[st.top()]){   //!st.empty()是必要的,因为访问不到就会报错result[st.top()]=i-st.top();st.pop();}st.push(i);    //先把比i小的都算完再pushi}return result;}
};

另外有一"错误"写法附上

//别这么写,虽然重复 push(i)，导致栈中可能会存储多个 i，但 result 本身并不会受影响
class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> st;vector<int> result(temperatures.size(),0);st.push(0);for(int i=1;i<temperatures.size();i++){//if(temperatures[i]>temperatures[st.top()]){while(!st.empty()&&temperatures[i]>temperatures[st.top()]){   //!st.empty()是必要的,因为访问不到就会报错result[st.top()]=i-st.top();st.pop();}st.push(i);    //先把比i小的都算完再pushi//}if(temperatures[i]==temperatures[st.top()]){st.push(i);}else if(temperatures[i]<temperatures[st.top()]){st.push(i);}}return result;}
};

496.下一个更大元素 I

力扣题目链接

注意题意,nums1是nums2的子集

要用一个unordered_map把nums1装起来,用nums2去做找更大元素的操作,然后去对接nums1里的元素

注意pop操作的位置

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> map;vector<int> result(nums1.size(),-1);stack<int> st;for(int i=0;i<nums1.size();i++){map[nums1[i]]=i;    //这样计是为了后面要找nums[i]}st.push(0);for(int i=1;i<nums2.size();i++){while(!st.empty()&&nums2[i]>nums2[st.top()]){if(map.count(nums2[st.top()])>0){result[map[nums2[st.top()]]]=nums2[i];}st.pop();     //放在if外面,保证每次都正确弹出}st.push(i);}return result;}
};

503.下一个更大元素II

力扣题目链接

可将原数组复制一份到自己后面计算,也可让i遍历nums两次,方法为i%nums.size(),举一个例子132132,后面处理最后一个2的时候不会造成正确的被覆盖,因为根据入栈规则,2会入栈,不会处理这里的result

//可将原数组复制一份到自己后面计算,也可让i遍历nums两次,方法为i%nums.size(),举一个例子132132,后面处理最后一个2的时候不会造成正确的被覆盖,因为根据入栈规则,2会入栈,不会处理这里的result
class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {stack<int> st;st.push(0);vector<int> result(nums.size(),-1);int length=nums.size();for(int i=1;i<nums.size()*2;i++){while(!st.empty()&&nums[i%length]>nums[st.top()]){result[st.top()]=nums[i%length];st.pop();}st.push(i%length);}return result;}
};