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

力扣-单调栈-739 每日温度

思路和时间复杂度

  1. 思路:要求找出第一个大的元素,因此从左往右找到比栈顶大的元素就收集结果并且更新栈,弹出栈顶,如果是小于等于栈的元素,就入栈,因为跟所求的元素没什么关系,此时栈内从栈顶到栈底是单调递增的
  2. 时间复杂度: O(n)      

代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> res(temperatures.size(), 0);
        stack<int> st;
        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()]){
                    res[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
        }

        return res;
    }
};


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

相关文章:

  • spring-aop笔记
  • 2023 年全国职业院校技能大赛(中职组)移动应用与开发赛项 赛题第十套
  • Python基础入门掌握(九)
  • 设计签到 用redis 和 MySQL
  • 目标检测中衡量模型速度和精度的指标:FPS和mAP
  • 软件测试之测试覆盖率
  • c++三级(枚举问题)
  • 普通enum和enum class的区别
  • Winfrom基础知识41-60
  • Uniapp 开发 App 端上架用户隐私协议实现指南
  • Halcon 和 opencv比有什么区别与优劣
  • python socket库详解
  • 【A2DP】深入解读A2DP中通用访问配置文件(GAP)的互操作性要求
  • 堆(Heap)和栈(Stack),这两者通常是指内存管理中两种不同的内存区域
  • 【Android】RuntimeShader 应用
  • 如何使用Jsoup提取商品信息:实战指南
  • Java Collection(3)——BinaryTree(二叉树)
  • std::merge和std::inplace_merge对比分析
  • 谷歌云服务器:服务器怎么安装???
  • 车载Android音频系统 AudioService