当前位置:网站首页>剑指 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的效率实在太低了……
边栏推荐
- tutle时钟改进版
- The end of the Internet is rural revitalization
- input显示当前选择的图片
- How to solve the component conflicts caused by scrollbars in GridView
- 配置交叉编译工具链和环境变量
- A little understanding of GSLB (global server load balance) technology
- fastjson
- Descriptive analysis of data distribution characteristics (data exploration)
- Use of hutool Pinyin tool
- BUU-Crypto-[HDCTF2019]basic rsa
猜你喜欢
(4) Canal multi instance use
Take you to quickly learn how to use qsort and simulate qsort
Component、Container容器常用API详解:Frame、Panel、ScrollPane
Detectron:训练自己的数据集——将自己的数据格式转换成COCO格式
Programmers don't talk about morality, and use multithreading for Heisi's girlfriend
光模块字母含义及参数简称大全
Simulink and Arduino serial port communication
一键过滤选择百度网盘文件
BUU-Crypto-[HDCTF2019]basic rsa
Grounding relay dd-1/60
随机推荐
Letter meaning and parameter abbreviation of optical module Daquan
光模塊字母含義及參數簡稱大全
APScheduler如何设置任务不并发(即第一个任务执行完再执行下一个)?
How to configure static IP for Kali virtual machine
Build an Internet of things infrared temperature measuring punch in machine with esp32 / rush to work after the Spring Festival? Baa, no matter how hard you work, you must take your temperature first
Install pytoch geometric
How to expand all collapse panels
Recommended system 1 --- framework
Invalid revision: 3.18.1-g262b901-dirty
Flask
[QT] create mycombobox click event
JS flattened array of number shape structure
HMS v1.0 appointment.php editid参数 SQL注入漏洞(CVE-2022-25491)
XII Golang others
1480. 一维数组的动态和
px em rem的区别
如何展开Collapse 的所有折叠面板
724. Find the central subscript of the array
Basic concept of bus
The data mark is a piece of fat meat, and it is not only China Manfu technology that focuses on this meat