当前位置: 首页 > article >正文

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

http://www.kler.cn/a/588428.html

相关文章:

  • 【专项测试】限流测试
  • Java算法OJ(12)
  • Vue 3 组件库主题化与可扩展性深度剖析:设计模式与实现策略 - 构建灵活适应多场景的组件库架构
  • Java缓存String(字符串常量池)、Integer (-128 到 127 )
  • 计算机基础:二进制基础12,十进制数转换为十六进制
  • 联想台式电脑启动项没有U盘
  • 【医学影像 AI】大型语言模型生成 ROP 患者信息材料的能力
  • 编程题《牛牛的链表删除》的python可以用非链表的方式
  • 某省政务信创案例:3阶段实施×5类工具链选型经验分享
  • Word 小黑第18套
  • 用DasViewer的时候3Dtiles 转osgb 可以直接指定目标坐标系吗?
  • 【c++】【智能指针】什么情况下不适合智能指针
  • C++之stack_queue扩展
  • 【VUE】day04-组件的生命周期、组件之间的数据共享、ref引用、购物车案例
  • Axure高级功能深度解析一一高效原型设计的利器
  • 怎样用Java实现快速排序与找到数组中第k小的值?
  • AI第一天 自我理解笔记--微调大模型
  • L1-093 猜帽子游戏
  • fpga系列 HDL:ModelSim 波形绘制tips
  • 【软件】免费的PDF全文翻译软件,能保留公式图表的样式