笔记:代码随想录算法训练营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;
    }
};