【LeetCode739】每日温度

这篇具有很好参考价值的文章主要介绍了【LeetCode739】每日温度。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1、题目描述

【题目链接】
给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

2、基本思路

 如果采用最简单最暴力的方法,就是从当前位置i的下一个位置i+1出发,找到第一个j,使得temperatures[j] > temperatures[i],这种方法最坏情况得时间复杂度为O(n^2)。那么,有没有更好得方法呢?答案是有的。
 采用单调栈的方法,维护一个从栈底到栈顶单调递减的序列,举个简单的例子,例如温度序列为【1,4,3,5,5,2,3,6】

  • 初始化,栈空;
  • 首先,栈空,1入栈(栈中元素[1]);
  • 第二个数4,与栈顶元素1比较,1<4,则出栈,且答案为res[1]=1,栈空结束比较,4入栈(栈中元素[4]);
  • 第三个数3,与栈顶元素4比较,4>3,3入栈;(栈中元素[4,3]);
  • 第四个数5,与栈顶元素3比较,3<5,3出栈,答案为res[3]=1;(栈中元素[4]);
  • 栈非空,继续与栈顶元素比较,4<5,4出战,答案为res[2]=2;(栈中元素[]);
  • 栈空,5入栈(栈中元素[5]);
  • 第五个元素5,与栈顶元素5比较,5>=5,5入栈,(栈中元素[5,5]);
  • 第六个元素2,与栈顶元素5比较,5>2,2入栈,(栈中元素[5,5,2]);
  • 第七个元素3,与栈顶元素2比较,2<3,2出栈,且答案为res[6]=1,(栈中元素[5,5]);
  • 栈非空,继续与栈顶元素5比较,5>3,3入栈,(栈中元素[5,5,3]);
  • 第八个元素6,与栈顶元素3比较,3<6,3出栈,且答案为res[7]=1,(栈中元素[5,5]);
  • 栈非空,与栈顶元素5比较,5<6,5出栈,且答案为res[4]=4,(栈中元素[5]);
  • 栈非空,与栈顶元素5比较,5<6,5出栈,且答案为res[5]=3,(栈中元素[]);
  • 栈为空且序列遍历结束
    最终答案为[1,2,1,4,3,1,1,0]

 同样,我们也可以维护一个从栈底到栈顶维护一个单调递减的序列,遍历的序列从右往左。

单调栈的基本思想——及时去掉无用的数据,保证栈中数据有序文章来源地址https://www.toymoban.com/news/detail-821177.html

3、代码实现

  • 方法一
vector<int> solve1(vector<int> &temperatures)
{
    int n = temperatures.size();
    vector<int> res(n,0);
    stack<int> st;
    for(int i =0;i<n;++i)
    {
        int t = temperatures[i];
        while(!st.empty() && t> temperatures[st.top()])
        {
            res[st.top()] = i-st.top();
            st.pop() ;
        }
        st.push(i);

    }
    
    return res;

}
  • 方法二
vector<int> solve(vector<int> &temperatures)
{
    int n = temperatures.size();
    vector<int> res(n,0);
    stack<int> st;
    for(int i =n-1;i>=0;i--)
    {
        int t = temperatures[i];
        while(!st.empty() && t>=temperatures[st.top()])
        {
            st.pop();
        }
        if(!st.empty())
        {
            res[i] = st.top()-i;
        }
        st.push(i);
    }
    return res;

}

到了这里,关于【LeetCode739】每日温度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录 739. 每日温度

    题目 给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。 示例 1: temperatures 示例 2: 输入: temperatures = [30,40,50,60] 输出: [1,1,1,0] 示例 3: 输入

    2024年01月18日
    浏览(35)
  • 二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

    各位CSDN的uu们你们好呀,今天小雅兰的内容仍然是二叉树和Leetcode每日一题,下面,就让我们进入二叉树的世界吧!!! 这个题目需要重新定义一个函数,函数参数需要有左子树和右子树,题目所给定的函数无法解决问题。 每个不为空的结点,都可以认为是一棵子树的根 

    2024年02月16日
    浏览(46)
  • 二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀,今天继续数据结构与算法专栏中的二叉树,下面,让我们进入二叉树的世界吧!!! 二叉树(上)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(41)
  • 【算法与数据结构】62、LeetCode不同路径

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :机器人只能向下或者向右移动,那么到达(i,j)位置的路径和(i-1,j)以及(i,j-1)有关。那么我们就得到的动态规划的表达式 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][

    2024年01月18日
    浏览(68)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(54)
  • 【算法与数据结构】112、LeetCode路径总和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题通过计算根节点到叶子节点路径上节点的值之和,然后再对比目标值。利用文章【算法和数据结构】257、LeetCode二叉树的所有路径中的递归算法。 这里要注意,默认路径之和是

    2024年02月11日
    浏览(53)
  • 【算法与数据结构】343、LeetCode整数拆分

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :博主做这道题的时候一直在思考,如何找到 k k k 个正整数, k k k 究竟为多少合适。从数学的逻辑上来说,将 n n n 均分为 k k k 个数之后, k k k 个数的乘积为最大(类似于相同周长

    2024年01月17日
    浏览(52)
  • 【算法与数据结构】494、LeetCode目标和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题和这道题【算法与数据结构】1049、LeetCode 最后一块石头的重量 II类似,同样可以转换成01背包问题。下面开始论述。假设添加正号的整数子集和为 p o s i t i v e positive p os i t

    2024年01月20日
    浏览(45)
  • 【算法与数据结构】474、LeetCode一和零

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题要找strs数组的最大子集,这个子集最多含有 m m m 个0和 n n n 个1。本题也可以抽象成一个01背包的问题。其中,strs内的元素就是物品,而 m m m 和 n n n 就是背包的维度。 d p [

    2024年01月22日
    浏览(42)
  • 【算法与数据结构】377、LeetCode组合总和 Ⅳ

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题明面上说是组合,实际上指的是排列。动态规划排列组合背包问题需要考虑遍历顺序。 d p [ i ] dp[i] d p [ i ] 指的是nums数组中总和为target的元素排列的个数。 d p [ i ] dp[i] d p [

    2024年01月23日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包