Leetcode739.每日温度

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

题目

给定一个整数数组 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

原题链接

Leetcode739.每日温度

思路1(暴力枚举)

  • 暴力

遍历每一个元素,然后再从当前元素往后找比它大的,找到之后记录下他俩位置的差值,然后停止内层循环,如果没找到默认为0。
Leetcode739.每日温度,c++,leetcode,数据结构
但是测试用例无法过完,O(N^2)的时间复杂度太高
Leetcode739.每日温度,c++,leetcode,数据结构

代码1

class Solution 
{
public:
    vector<int> dailyTemperatures(vector<int>& a) 
    {
        int n = a.size();
        vector<int> res(n, 0);//用0初始化一个大小跟a一样得数组;
        for(int i = 0; i < n; i++)//遍历第一个元素
        {
            for(int j = i + 1;j < n; j++)//从当前元素得下一个元素开始找比当前元素大的第一个
            {
                if(a[j] > a[i]) 
                {
                    res[i] = j - i;
                    break;
                }
            }
        }
        return res;
    }
};

思路2(单调栈)

遍历整个数组,如果栈不空,且当前数字大于栈顶元素,取出栈顶元素由于当前数字大于栈顶元素的数字,而且一定是第一个大于栈顶元素的数,直接求出下标差就是二者的距离。
看向新的栈顶元素,直到当前数字小于等于栈顶元素停止,然后将数字入栈,每个数字和第一个大于它的数的距离也可以算出来。
Leetcode739.每日温度,c++,leetcode,数据结构
Leetcode739.每日温度,c++,leetcode,数据结构
Leetcode739.每日温度,c++,leetcode,数据结构
O(N)的时间复杂度文章来源地址https://www.toymoban.com/news/detail-823937.html

代码2

class Solution 
{
public:
    vector<int> dailyTemperatures(vector<int>& a) 
    {
        vector<int> res(a.size(), 0);//开一个跟a大小一样的答案是数组
        stack<int> st;   //单调栈

        for(int i = 0; i < a.size(); i++)遍历数组
        {
            while(!st.empty() && a[i] > a[st.top()])//如果栈不为空并且当前元素大于栈顶元素,那么计算栈顶元素的res并且出栈顶元素
            {
                res[st.top()] = i - st.top();
                st.pop();
            }
            //如果当前元素小于或者等于栈顶元素,那么当前元素下标入栈
            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日
    浏览(33)
  • 二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

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

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

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

    2024年02月17日
    浏览(38)
  • leetcode:每日温度---单调栈

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

    2024年01月25日
    浏览(54)
  • Leetcode 剑指 Offer II 038. 每日温度

    题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 请根据每日 气温 列表 temperatures ,重新生成一个列表,要求其对应位置的输出为:要想观测到更高的

    2024年02月14日
    浏览(44)
  • 【LeetCode】《LeetCode 101》第十一章:妙用数据结构

    C++ 提供的数据结构包括: Sequence Containers:维持顺序的容器。 vector: 动态数组 ,用于 O(1) 的随机读取。因为大部分算法的时间复杂度都会大于 O(n) ,因此我们经常新建 vector 来存储各种数据或中间变量。 list: 双向链表 ,也可以当作 stack 和 queue 来使用。由于 LeetCode 的题目

    2024年02月13日
    浏览(140)
  • 【数据结构 | 链表】leetcode 2. 两数相加

    个人主页:兜里游客棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里游客棉花糖 原创 收录于专栏【LeetCode】 原题链接:点击直接跳转到该题目 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位

    2024年02月05日
    浏览(52)
  • 【LeetCode】数据结构题解(5)[分割链表]

    所属专栏:玩转数据结构题型 博主首页:初阳785 代码托管:chuyang785 感谢大家的支持,您的点赞和关注是对我最大的支持!!! 博主也会更加的努力,创作出更优质的博文!! 关注我,关注我,关注我,重要的事情说三遍!!!!!!!! 分割链表 给你一个链表的头节点

    2024年02月04日
    浏览(48)
  • 【LeetCode】数据结构题解(6)[回文链表]

    所属专栏:玩转数据结构题型 博主首页:初阳785 代码托管:chuyang785 感谢大家的支持,您的点赞和关注是对我最大的支持!!! 博主也会更加的努力,创作出更优质的博文!! 关注我,关注我,关注我,重要的事情说三遍!!!!!!!! 回文链表 给定一个链表的 头节点

    2024年02月03日
    浏览(46)
  • 【算法与数据结构】112、LeetCode路径总和

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

    2024年02月11日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包