当前位置:网站首页>剑指 Offer II 038. 每日温度
剑指 Offer II 038. 每日温度
2022-07-04 05:46:00 【小白码上飞】
概要
使用栈,遍历数组,比较当前数字是否比栈顶元素大。大则出栈处理,直到栈空或者当前数字小于栈顶数字时,将当前数字入栈。
题目
请根据每日 气温 列表 temperatures ,重新生成一个列表,要求其对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。
链接:https://leetcode.cn/problems/iIQa4I
思路
其实和行星碰撞的很像。
我们用一个栈来保存数组中每个元素的下标,从做开始遍历数组。
- 如果栈为空,则入栈。
- 如果栈不为空,比较栈顶和当前元素的大小
- 如果当前元素大,则用当前元素下标和栈顶下标相减,得到栈顶元素“需要等待的天数”。之后再继续和栈里的元素比较大小。
- 如果当前元素小,则入栈。
这样始终让栈顶的元素是最小的,一旦有更大值出现,就把栈中比他小的值都处理掉。
解法:单调栈
代码
public int[] dailyTemperatures2(int[] temperatures) {
int[] result = new int[temperatures.length];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < temperatures.length; i++) {
if (stack.isEmpty()) {
stack.push(i);
continue;
}
int current = temperatures[i];
while (!stack.isEmpty() && current > temperatures[stack.peek()]) {
int index = stack.pop();
result[index] = i - index;
}
stack.push(i);
}
// 处理观测不到高温的日子
while (!stack.isEmpty()) {
result[stack.pop()] = 0;
}
return result;
}
执行结果
这里注意,直接使用了Deque来代替Stack,因为Stack的效率实在太低了……
边栏推荐
- HMS v1.0 appointment.php editid参数 SQL注入漏洞(CVE-2022-25491)
- LC weekly 300
- 力扣(LeetCode)184. 部门工资最高的员工(2022.07.03)
- 【微服务】Nacos集群搭建以及加载文件配置
- Basic concept of bus
- Simulink and Arduino serial port communication
- One click filtering to select Baidu online disk files
- Thinkphp6.0 middleware with limited access frequency think throttle
- Viewing and using binary log of MySQL
- 报错cvc-complex-type.2.4.a: 发现了以元素 ‘base-extension‘ 开头的无效内容。应以 ‘{layoutlib}‘ 之一开头。
猜你喜欢
光模块字母含义及参数简称大全
(4) Canal multi instance use
卸载Google Drive 硬盘-必须退出程序才能卸载
Signification des lettres du module optique et abréviation des paramètres Daquan
Solar insect killing system based on single chip microcomputer
Kubernets first meeting
1480. Dynamic sum of one-dimensional array
[QT] create mycombobox click event
Grounding relay dd-1/60
Kubernets first meeting
随机推荐
fastjson
509. 斐波那契数、爬楼梯所有路径、爬楼梯最小花费
BUU-Crypto-[HDCTF2019]basic rsa
left_ and_ right_ Net normal version
VB.net 简单的处理图片,黑白(类库——7)
LC weekly 300
Invalid revision: 3.18.1-g262b901-dirty
Flask
十二. golang其他
How to get the parent node of all nodes in El tree
APScheduler如何设置任务不并发(即第一个任务执行完再执行下一个)?
How to implement lazy loading in El select (with search function)
How to use postman to realize simple interface Association [add, delete, modify and query]
Compound nonlinear feedback control (2)
webrtc 快速搭建 视频通话 视频会议
(4) Canal multi instance use
el-select如何实现懒加载(带搜索功能)
Enterprise level log analysis system elk (if things backfire, there must be other arrangements)
配置交叉编译工具链和环境变量
Leetcode 184 Employees with the highest wages in the Department (July 3, 2022)