[每日算法 - 阿里机试] leetcode739. 每日温度

入口

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/daily-temperatures/description/

题目描述

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

方法一:暴力法

        该算法使用两个嵌套循环,对于每一天,它都会遍历后续的天数来查找第一个温度升高的日子。测试集足够大时,此方法在leetcode中会超出时间限制。

Java实例

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length]; // 用于存储结果的数组
        
        for (int i = 0; i < temperatures.length; i++) {
            int temp = 0; // 用于记录等待的天数
            
            for (int j = i+1; j < temperatures.length; j++) {
                if (temperatures[j] > temperatures[i]) {
                    temp = j - i; // 如果找到升高的温度,则计算等待的天数
                    break; // 跳出内层循环,因为已经找到了升高的温度
                }
            }
            
            res[i] = temp; // 将等待的天数存储在结果数组中
        }
        
        return res; // 返回结果数组
    }
}

复杂度分析

  • 时间复杂度:O(n^2),其中 n 是温度数组的长度。因为对于每一天,最坏情况下需要遍历数组的其余部分来找到温度升高的日子。
  • 空间复杂度:O(1),只使用了常量级的额外空间。

方法二:暴力法改进-辅助数组

        该方法是暴力法的改进方法,其核心思想是利用辅助数组 next 来记录每个温度后面出现的更高温度的索引位置,从而避免了嵌套循环。

辅助数组 next: 这个数组的索引表示温度值,数组中的值表示该温度值在原数组中出现的索引位置。初始化为最大值,表示当前温度后面没有更高的温度。

逆序遍历原数组: 从数组末尾开始向前遍历,这是因为我们需要找的是每个温度后面第一次出现的更高温度,逆序遍历可以确保我们从后往前找到更高温度。

查找更高温度的索引: 对于每个温度,我们不需要遍历其后面的所有温度,而是直接查找辅助数组 next 中大于当前温度的最小索引值,即下一个更高温度的索引。

通过这种方法,我们只需要一次遍历原数组,时间复杂度为 O(n),大大提高了效率。

Java示例

    public static int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length]; // 用于存储结果的数组
        int[] next = new int[101]; // 辅助数组,用于存储下一个更暖和的温度的索引

        // 初始化辅助数组为最大值,表示没有更暖和的温度
        Arrays.fill(next, Integer.MAX_VALUE);

        // 从数组末尾开始遍历
        for (int i = length - 1; i >= 0; --i) {
            int warmerIndex = Integer.MAX_VALUE; // 用于记录下一个更暖和的温度的索引, 初始值设为 Integer.MAX_VALUE,表示初始情况下没有更高温度。

            // 遍历当前温度之后的所有可能温度,最高温度不会超过 100
            for (int t = temperatures[i] + 1; t <= 100; ++t) {
                if (next[t] < warmerIndex) { //找到了比当前温度更高的温度,并且它的索引比之前记录的更高温度索引还要小,就更新 warmerIndex。这样,warmerIndex 就始终记录着当前温度后面第一次出现更高温度的索引位置。
                    warmerIndex = next[t];   // 找到下一个更暖和的温度的索引
                }
            }

            // 如果找到了更暖和的温度,则计算等待的天数
            if (warmerIndex < Integer.MAX_VALUE) {
                ans[i] = warmerIndex - i;
            }

            // 更新辅助数组,将当前温度的索引存储在相应的位置
            next[temperatures[i]] = i;
        }

        return ans; // 返回结果数组
    }

复杂度分析

  • 时间复杂度:O(nm),其中 n 是温度列表的长度,m 是数组 next 的长度,在本题中温度不超过 100,所以 m 的值为 100。反向遍历温度列表一遍,对于温度列表中的每个值,都要遍历数组 next 一遍。
  • 空间复杂度:O(m),其中 m 是数组 next 的长度。除了返回值以外,需要维护长度为 m 的数组 next 记录每个温度第一次出现的下标位置。

方法三:单调栈

​​​​​​​

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 创建一个数组用于存储结果,长度与温度数组相同
        int[] ans = new int[temperatures.length];
        // 创建一个栈用于存储温度数组的索引
        Deque<Integer> stack = new LinkedList<>();
        // 遍历温度数组
        for(int i = 0; i < temperatures.length; ++i){
            // 如果栈不为空并且当前温度大于栈顶温度
            while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                // 弹出栈顶索引,计算等待天数并记录到结果数组中
                int preIndex = stack.pop();
                ans[preIndex] = i - preIndex;
            }
            // 将当前索引入栈
            stack.push(i);
        }
        // 返回结果数组
        return  ans;
    }
}

时间复杂度:O(n),其中 nnn 是温度列表的长度。正向遍历温度列表一遍,对于温度列表中的每个下标,最多有一次进栈和出栈的操作。

空间复杂度:O(n)O,其中 nnn 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

单调栈练习题
leetcode496.下一个更大元素1
leetcode901.股票价格跨度
leetcode42.接雨水
leetcode84.柱状图中最大的矩形

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/525606.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

深度学习理论基础(七)Transformer编码器和解码器

学习目录&#xff1a; 深度学习理论基础&#xff08;一&#xff09;Python及Torch基础篇 深度学习理论基础&#xff08;二&#xff09;深度神经网络DNN 深度学习理论基础&#xff08;三&#xff09;封装数据集及手写数字识别 深度学习理论基础&#xff08;四&#xff09;Parse…

UE5、CesiumForUnreal实现加载建筑轮廓GeoJson数据生成白模功能

1.实现目标 在UE5.3中,通过加载本地建筑边界轮廓面GeoJson数据,获取底面轮廓和楼高数据,拉伸生成白模,并支持点选高亮。为防止阻塞Game线程,使用了异步任务进行优化,GIF动图如下所示: 其中建筑数量:128871,顶点索引数量:6695748,三角面数量:2231916,顶点数量:165…

golang 归并回源策略

前言 下面是我根据业务需求画了一个架构图&#xff0c;没有特别之处&#xff0c;很普通&#xff0c;都是我们常见的中间件&#xff0c;都是一些幂等性GET 请求。有一个地方很有意思&#xff0c;从service 分别有10000 qps 请求到Redis&#xff0c;并且它们的key 是一样的。这样…

CSS - 你遇到过动画卡顿的问题吗

难度级别:中高级及以上 提问概率:70% 回答这道题,首先要说的就是,浏览器在每一帧动画里大概做了什么事情。首先浏览器会执行Javascript,或是操作DOM元素,紧接着需要对DOM元素进行样式计算,当计算完成后,就需要针对DOM元素的位置以及大小…

2024年MathorCup妈妈杯数学建模思路D题思路解析+参考成品

1 赛题思路 (赛题出来以后第一时间在群内分享&#xff0c;点击下方群名片即可加群) 2 比赛日期和时间 报名截止时间&#xff1a;2024年4月11日&#xff08;周四&#xff09;12:00 比赛开始时间&#xff1a;2024年4月12日&#xff08;周五&#xff09;8:00 比赛结束时间&…

oracle hang分析使用

oracle hang分析测试 使用hang分析大部分原因在于产生锁资源的争用 1-2:只有hanganalyze输出&#xff0c;不dump任何进程 3&#xff1a;Level2Dump出在IN_HANG状态的进程 4&#xff1a;Level3Dump出在等待链里面的blockers(状态为LLEAF/LEAF_NW/IGN_DMP&#xff09; 5&…

软件设计师29--并发控制

软件设计师29--并发控制 考点1&#xff1a;事务的特性例题&#xff1a; 考点2&#xff1a;并发问题并发产生的问题丢失更新不可重复读问题读“脏”数据 考点3&#xff1a;封锁协议例题&#xff1a; 考点1&#xff1a;事务的特性 原子性&#xff08;Atomicity&#xff09;&…

好文阅读-数据库-CREATE TABLE AS

添加链接描述 收获如下&#xff1a; 1 DROP DELETE TRUNCATE对比 2 CREATE TABLE AS 这种方式创建表不会复制表的索引&#xff0c;主键&#xff0c;外键约束&#xff0c;包括自增ID。因此应该使用 CREATE TABLE LIKE。 3 数据的处理可以通过建立临时表的方式&#xff0c;之后还…

【实战解析】YOLOv9全流程训练至优化终极指南

【实战解析】YOLOv9全流程训练至优化终极指南 0.引言1.环境准备2.数据预处理&#xff08;1&#xff09;数据准备&#xff08;2&#xff09;按比例划分数据集&#xff08;3&#xff09;xml转txt脚本&#xff08;4&#xff09;配置文件 3.模型训练&#xff08;1&#xff09;单GPU…

超越基准 | 基于每个高斯变形的3D高斯溅射方法及其高效训练策略

作者&#xff1a;小柠檬 | 来源&#xff1a;3DCV 在公众号「3DCV」后台&#xff0c;回复「原论文」可获取论文pdf 添加微信&#xff1a;dddvision&#xff0c;备注&#xff1a;3D高斯&#xff0c;拉你入群。文末附行业细分群 详细内容请关注3DCV 3D视觉精品课程&#xff1a;…

ctfshow web入门 命令执行 web53--web77

web53 日常查看文件 怎么回事不让我看十八 弄了半天发现并不是很对劲&#xff0c;原来我发现他会先回显我输入的命令再进行命令的回显 ?cnl${IFS}flag.php||web54 绕过了很多东西 基本上没有什么命令可以用了但是 grep和?通配符还可以用 ?cgrep${IFS}ctfshow${IFS}???…

JavaCollection集合--单列集合——JavaCollections类

目录 集合--->容器 代码 运行 Java集合API 单列集合 Collectio接口 List接口实现类 ArrayList 数组实现 概念 代码 运行 代码 ArrayList方法 代码 运行 LinkedList 链表实现 概念 代码 运行 Vector 数组实现 概念 代码 运行 List接口集合…

知识推理技术解析与实战

目录 一、引言二、知识推理基础知识表示方法本体论语义网络图形数据库 推理机制概述演绎推理归纳推理类比推理 实践代码示例 三、知识推理的核心技术自动推理系统规则引擎推理算法 知识图谱的运用构建知识图谱知识推理与查询 推理算法深度分析转导推理逻辑推理概率推理 实践代码…

java智慧校园系统源码+SaaS智慧学校系统源码+PC端

java智慧校园系统源码SaaS智慧学校系统源码PC端 有演示&#xff0c;可正常上线运营可授权PC端&#xff0c;SaaS服务模式开发环境&#xff1a;Javaspringbootvueelement-uimysql开发语言&#xff1a;JavaspringbootVUE 小程序 全套源码 建设一个一流的智慧校园&#xff0c;使先进…

MuJoCo 入门教程(五)Python 绑定

系列文章目录 前言 本笔记本提供了使用本地 Python 绑定的 MuJoCo 物理入门教程。 版权声明 DeepMind Technologies Limited 2022 年版权所有。 根据 Apache License 2.0 版&#xff08;以下简称 "许可协议"&#xff09;授权&#xff1b;除非遵守许可协议&am…

操作系统1

概念 操作系统 组织和管理计算机系统中的软件和硬件&#xff0c;组织计算机系统工作流程、控制程序执行&#xff0c;提供给用户工作环境和友好的接口。 3个作用&#xff1a; 管理计算机中运行的程序和分配各种软硬件资源为用户提供友善的人机洁界面为应用程序的开发和运行提供…

二维相位解包理论算法和软件【全文翻译- 噪声滤波(3.53.6)】

3.5 噪音过滤 在本节中,我们将简要讨论相位数据的滤波问题。除了提高信噪比之外,噪声滤波还有助于减少残差的数量,从而大大简化相位解包过程。不过,我们必须注意到一个重要的问题。正如我们在第 1 章中指出的,相位本身并不是信号。它只是信号的一种属性。因此,应该过滤的…

ACM ICPS独立出版 | 第三届智能无人系统与人工智能国际会议(SIUSAI 2024)

会议简介 Brief Introduction 2024年第三届智能无人系统与人工智能国际会议(SIUSAI 2024) 会议时间&#xff1a;2024年5月17日-19日 召开地点&#xff1a;中国青岛 大会官网&#xff1a;www.siusai.org 2024年第三届智能无人系统与人工智能国际会议(SIUSAI 2024)由青岛大学主办…

基于java JSP 实现的固定资产管理系统

开发语言&#xff1a;Java 框架&#xff1a;ssm 技术&#xff1a;JSP JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea 系统展示 前台首页功能模块 固…

UV胶水能够粘接聚苯乙烯PS吗?

UV胶水能够粘接聚苯乙烯PS吗&#xff1f; 聚苯乙烯&#xff08;Polystyrene&#xff0c;简称PS&#xff09;是一种常见的合成聚合物&#xff0c;属于热塑性塑料。它是由苯乙烯单体聚合而成的&#xff0c;具有轻质、透明或半透明、电绝缘性好等特点。常见: 包装材料白色泡沫塑料…