( 栈和队列) 739. 每日温度 ——【Leetcode每日一题】

news/2024/4/15 13:01:13

❓739. 每日温度

难度:中等

给定一个整数数组 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 < = t e m p e r a t u r e s . l e n g t h < = 1 0 5 1 <= temperatures.length <= 10^5 1<=temperatures.length<=105
  • 30 <= temperatures[i] <= 100

💡思路:

法一:暴力

大多数人看到该题目的第一思路可能就是暴力求解,即对每个数都往后一个一个查找,直到找到比当前数大的为止;

我们可以再多想一步,能否利用前面的搜索信息,从而降低搜索量,这时我们就可以从后往前遍历该数组:

  • 除了最后一个元素外,对每元素都先和紧接该元素之后的比较,如果后一个元素大于当前元素,我们就找到了下一个最高温度,结果保存为1(这也是我们最希望处理的);
  • 如果紧接该元素i之后的元素小于等于当前元素,那么我们就查找紧接该元素之后的元素的下一个更高温度(因为我们是从后往前遍历,所以后面的结果我们都已经得到。)直到找到比i更高温度,或者找到最后都没有,则结果为0

法二:单调栈

观察发现,我们要找的结果,可以由数组的索引获得,如果这一天的温度比前一天的温度高,前一天的结果就等于这一天的数组索引减去前一天的数组索引,结果为1

  • 所以我们可以利用栈,保存数组索引,如果当前索引的温度,高于栈顶索引对应的温度,则栈顶索引处的结果ans[indexs.top()]就等于当前索引curIndex 减去 栈顶索引值indexs.top(),然后出栈,再和栈顶比较,直到不高于栈顶索引对应的温度;
  • 如果不高于栈顶索引对应的温度,则当前索引curIndex 入栈;

🍁代码:(Java、C++)

法一:暴力
Java

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] ans = new int[n];ans[n - 1] = 0;for (int i = n - 2; i >= 0; i--) {if (temperatures[i] < temperatures[i + 1]) {ans[i] = 1;}else {int j = i + 1;ans[i] = 1 + ans[j];j += ans[j];while (j < n) {if (temperatures[i] < temperatures[j]) {break;}else if (temperatures[i] >= temperatures[j] && ans[j] != 0) {ans[i] += ans[j];j += ans[j];}else{ans[i] = 0;break;}}}}return ans;}
}

C++

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n);ans[n - 1] = 0;for (int i = n - 2; i >= 0; i--) {if (temperatures[i] < temperatures[i + 1]) {ans[i] = 1;}else {int j = i + 1;ans[i] = 1 + ans[j];j += ans[j];while (j < n) {if (temperatures[i] < temperatures[j]) {break;}else if (temperatures[i] >= temperatures[j] && ans[j] != 0) {ans[i] += ans[j];j += ans[j];}else{ans[i] = 0;break;}}}}return ans;}
};

法二:单调栈
Java

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] dist = new int[n];Stack<Integer> indexs = new Stack<>();for (int curIndex = 0; curIndex < n; curIndex++) {while (!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]) {int preIndex = indexs.pop();dist[preIndex] = curIndex - preIndex;}indexs.add(curIndex);}return dist;}
}

C++

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n);stack<int> indexs;for (int curIndex = 0; curIndex < n; curIndex++) {while (!indexs.empty() && temperatures[curIndex] > temperatures[indexs.top()]) {ans[indexs.top()] = curIndex - indexs.top();indexs.pop();}indexs.push(curIndex);}return ans;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 是温度列表的长度。正向遍历温度列表一遍,对于温度列表中的每个下标,最多有一次进栈和出栈的操作。暴力法小于 O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度 O ( n ) O(n) O(n),其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/54854.html

相关文章

linux共享文件夹?

linux共享文件夹&#xff1f; 在Linux中&#xff0c;可以使用Samba或NFS等服务来共享文件夹。 使用Samba共享文件夹 Samba是一种允许Windows和Linux之间共享文件和打印机的服务。以下是在Linux中使用Samba共享文件夹的步骤&#xff1a; 安装Samba服务&#xff1a; 在Debia…

OtterCTF

五年前的老题了&#xff0c;但还是值得一做&#xff0c;内存取证yyds! What the password? 取电脑的密码 先看缓存在内存中的注册表的偏移量 volatility_2.6_win64_standalone -f 1.vmem --profileWin7SP1x64 hivelist关注到SAM(账户密码表)和system volatility_2.6_win6…

HashMap详解

手撕HashMap源码 HashMap一直是面试的重点。今天我们来了解了解它的源码吧&#xff01; 首先看一下Map的继承结构图 源码分析 什么是哈希 **Hash&#xff0c;一般翻译做“散列”&#xff0c;也有直接音译为“哈希”的&#xff0c;就是把任意长度的输入&#xff0c;通过散列算…

知识图谱实战应用7-最完整的常用Cypher查询语句与实际应用

大家好,我是微学AI,今天给大家介绍一下知识图谱实战应用7-常用的Cypher查询语句与实际应用。Cypher 是 Neo4j 图数据库的查询语言,它是一种声明式的图形查询语言,使用 ASCII 码字符来描述数据模式和数据操作。Cypher 具有可读性强、易于理解和学习、功能丰富等特点。 一、…

A 股指数分时行情数据 API 数据接口

A 股指数分时行情数据 API 数据接口 多维度分时指标&#xff0c;指数分时&#xff0c;多时间区间查询参数。 1. 产品功能 支持所有指数数据查询&#xff1b;支持指数分时数据查询&#xff1b;多时间维度分时数据&#xff1b;多维度的统计时间以及数据结果&#xff1b;秒级查询…

Netty内存管理--内存池空间规格化SizeClasses

一、规格化 内存池类似于一个内存零售商, 从操作系统中申请一整块内存, 然后对其进行合理分割, 将分割后的小内存返回给程序。这里存在3个尺寸: 分割尺寸: 底层内存管理的基本单位, 比如常见的以页为单位分配, 但是页的大小是灵活的;申请尺寸: 内存使用者希望申请到的内存大小…

创新引擎:云计算五大优势解锁企业潜力

文章目录 创新引擎:云计算五大优势解锁企业潜力一、前言二、云计算的基础概念三、 企业采用云计算的优势四、 行业应用案例五、未来发展与挑战六、总结 创新引擎:云计算五大优势解锁企业潜力 一、前言 信息技术应用为企业带来了巨大便利,但也面临诸如高成本、低效率、信息孤岛…

自然语言模型的哲学小谈

近期&#xff0c;以chatGPT为代表的大语言模型表现非常惊艳。“In Context Learning”、“Instruct”1&#xff0c;以及推理能力&#xff0c;很难不让我们期待未来人工智能的发展&#xff0c;同时冷静思考一下为什么自然语言模型能够取得巨大进步。 文章目录 1 放空大脑从0开始…

【无人机】无人机平台的非移动 GPS 干扰器进行位置估计的多种传感器融合算法的性能分析(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

gitlab部署及整合Jenkins持续构建(四)sonarqube9.9安装和使用(一步一坑)

文章目录 postgresql13.0安装1、配置postgresql数据库2、进入postgresql创建数据库 代码质量管理平台--sonarqube安装1、前置依赖下载2、安装unzip并解压sonarqube并移动到/usr/local&#xff1a;3、修改sonarqube相应的配置4、新增用户&#xff0c;并将目录所属权赋予该用户&a…

系统集成项目管理工程师 笔记(第17章:信息系统安全管理)

文章目录 信息安全属性及目标&#xff08;1&#xff09;保密性&#xff08;Confidentiality&#xff09;&#xff08;2&#xff09;完整性&#xff08;Integrity&#xff09;&#xff08;3&#xff09;可用性&#xff08;Availability&#xff09;&#xff08;4&#xff09;其他…

Python学习:Anaconda23.3.1+spyder5.4.3+Python3.10.11环境配置

问题1&#xff1a;Anaconda安装配置教程&#xff08;真的非常详细的安装过程&#xff0c;还带环境配置&#xff09; 【参考文献】本文链接&#xff1a;Windows安装Anaconda使用教程_在奋斗的大道的博客-CSDN博客 问题2&#xff1a;Anaconda半天打不开&#xff0c;就在这转啊转…

【是C++,不是C艹】 省缺参数 | 函数重载 | 内联函数

&#x1f49e;&#x1f49e;欢迎来到 Claffic 的博客 &#x1f49e;&#x1f49e; &#x1f449; 专栏&#xff1a;《是C&#xff0c;不是C艹》&#x1f448; 前言&#xff1a; 上期&#xff0c;我带大家给C打了招呼&#xff0c;捎带着认识了命名空间和输入输出&#xff0c;那…

【服务器】威联通NAS文件共享 - 搭建SFTP服务并内网穿透实现在外远程访问

Yan-英杰的主页 悟已往之不谏 知来者之可追 C程序员&#xff0c;2024届电子信息研究生 目录 前言 1. 威联通NAS启用SFTP 2. 测试局域网访问 3. 内网穿透 3.1 威联通安装cpolar内网穿透 3.2 创建隧道 3.3 测试公网远程访问 4. 配置固定公网TCP端口地址 4.1 保留一个固定TCP…

【Golang开发入门】一篇文章弄懂:值类型、指针类型

博主简介&#xff1a;努力学习的大一在校计算机专业学生&#xff0c;热爱学习和创作。目前在学习和分享&#xff1a;数据结构、Go&#xff0c;Java等相关知识。博主主页&#xff1a; 是瑶瑶子啦所属专栏: Go语言核心编程近期目标&#xff1a;写好专栏的每一篇文章 目录 一、前言…

Linux进程概念——其二

目录 环境变量 基本概念 常见环境变量 查看环境变量方法 测试PATH&#xff3b;重点&#xff3d; 测试HOME 和环境变量相关的命令 环境变量的组织方式 通过代码获取环境变量 通过系统调用获取或设置环境变量 环境变量通常是具有全局属性的&#xff3b;重点&#xff3d…

Java中的三元运算,以后用得到

目录 前言一、Java运算符二、Java三元运算符1.三元运算符介绍2.三元运算嵌套3.三元运算 VS if-else 总结 前言 Java 中的三元运算&#xff0c;平时也叫做三目运算&#xff0c;大家了解吗&#xff1f;下面就详细介绍一下&#xff0c;以后在项目编程中用得到。 一、Java运算符 …

上传ipa到appstore详细步骤

使用hbuilderx或apicloud云打包后&#xff0c;会生成一个ipa文件&#xff0c;而iphone是无法直接安装这个ipa文件的&#xff0c;需要将这个ipa文件上架&#xff0c;才能安装使用。那么如何上架呢&#xff1f; hbuilderx和apicloud并没有上架的教程&#xff0c;而苹果官方是推荐…

可以一学的代码优化小技巧:减少if-else冗余

前言 if-else 语句对于程序员来说&#xff0c;是非常非常熟悉的一个判断语句&#xff0c;我们在日常开发和学习中都经常看见它&#xff0c;if-else语句主要用于需要做出选择的地方进行判断&#xff0c;这里就不再赘述if-else语法和特点了。 ​ 我们在写代码&#xff08;如图下…

【安卓源码】Binder机制3 -- Binder线程池

Binder本身是C/S架构&#xff0c;就可能存在多个Client会同时访问Server的情况。 在这种情况下&#xff0c;如果Server只有一个线程处理响应&#xff0c;就会导致客户端的请求可能需要排队而导致响应过慢的现象发生。解决这个问题的方法就是引入多线程。【多个客户端不同线程去…
最新文章