当前位置:网站首页>【Hot100】739. Daily temperature
【Hot100】739. Daily temperature
2022-07-06 06:51:00 【Wang Liuliu's it daily】
739. Daily temperature
Given an array of integers temperatures , Indicates the daily temperature , Returns an array answer , among answer[i] Refers to the i God , The next higher temperature appears in a few days . If the temperature doesn't rise after that , Please use... In this position 0 Instead of .
Input : temperatures = [73,74,75,71,69,72,76,73]
Output : [1,1,4,2,1,1,0,0]
Topic understanding :
For input 73, It needs to After a day Until the temperature rises , That is, the next day , The temperature rises to 74 , So the corresponding result is 1.
For input 74, It needs to the One day Until the temperature rises , On the third day , The temperature rises to 75 , So the corresponding result is 1.
For input 75, It passes by 1 The temperature was found to be 71, No more than it , Keep waiting , always Wait four days , Wait until the temperature rises on the seventh day , The temperature rises to 76 , So the corresponding result is 4 .
For input 71, It passes by 1 The temperature was found to be 69, No more than it , Keep waiting , always Waited two days. , Wait until the temperature rises on the sixth day , The temperature rises to 72 , So the corresponding result is 2 .
For input 69, it After a day It turns out that the temperature is 72, It's over it , So the corresponding result is 1 .
For input 72, it After a day It turns out that the temperature is 76, It's over it , So the corresponding result is 1 .
For input 76, follow-up There is no temperature Can surpass it , So the corresponding result is 0 .
For input 73, follow-up There is no temperature Can surpass it , So the corresponding result is 0 .
idea : For each temperature value Search backward in turn , Find a value higher than the current temperature , This is the easiest way to think about it .
principle : From left to right, all numbers except the last one are traversed once , The result of the last data must be 0, There is no need to calculate .
When traversing , Every number goes backward , Until we find a larger number , Count frequency Is the corresponding output value .
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len = temperatures.length;
int[] res = new int[len];
for(int i=0;i<len;i++){
int cur = temperatures[i];
if(cur < 100){
for(int j=i+1;j<len;j++){
if(temperatures[j] > cur){
res[i] = j-i;
break;
}
}
}
}
return res;
}
}
Use the stack to solve :
Decrement stack : There are only diminishing elements in the stack .
Traverse the entire array , If the stack is not empty , And the current number is greater than the stack top element , So if you go directly to the stack, it's not Decrement stack , So you need to take out the top element of the stack , Because the current number is larger than the number of the top element of the stack , And it must be the first one greater than the number of elements at the top of the stack , Directly find out the subscript difference is the distance between the two .
Keep looking at the new stack top elements , Until the current number is less than or equal to the top element of the stack , Then put the numbers on the stack , This keeps the decrement stack going , And the distance between each number and the first number greater than it can also be calculated .
class Solution {
public int[] dailyTemperatures(int[] T) {
Stack<Integer> stack = new Stack<>();
int length = T.length;
int[] result = new int[length];
for (int i = 0; i < length; i++) {
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
int pre = stack.pop();
result[pre] = i - pre;
}
stack.add(i);
}
return result;
}
}
边栏推荐
- Database basics exercise part 2
- Apache dolphin scheduler source code analysis (super detailed)
- Leetcode daily question (971. flip binary tree to match preorder traversal)
- Day 245/300 JS foreach data cannot be updated to the object after multi-layer nesting
- 基于PyTorch和Fast RCNN快速实现目标识别
- MySQL high frequency interview 20 questions, necessary (important)
- Day 246/300 ssh连接提示“REMOTE HOST IDENTIFICATION HAS CHANGED! ”
- Redis Foundation
- 一文读懂简单查询代价估算
- 《从0到1:CTFer成长之路》书籍配套题目(周更)
猜你喜欢
【软件测试进阶第1步】自动化测试基础知识
Do you really know the use of idea?
Phishing & filename inversion & Office remote template
[ 英语 ] 语法重塑 之 英语学习的核心框架 —— 英语兔学习笔记(1)
Apache DolphinScheduler源码分析(超详细)
LeetCode - 152 乘积最大子数组
【服务器数据恢复】IBM服务器raid5两块硬盘离线数据恢复案例
Bitcoinwin (BCW): 借贷平台Celsius隐瞒亏损3.5万枚ETH 或资不抵债
顶测分享:想转行,这些问题一定要考虑清楚!
Reflex WMS中阶系列3:显示已发货可换组
随机推荐
Latex文字加颜色的三种办法
What are the commonly used English words and sentences about COVID-19?
Simple query cost estimation
【Hot100】739. 每日溫度
Pymongo gets a list of data
Attributeerror: can 't get attribute' sppf 'on < module' models. Common 'from' / home / yolov5 / Models / comm
将ue4程序嵌入qt界面显示
指尖上的 NFT|在 G2 上评价 Ambire,有机会获得限量版收藏品
Successfully solved typeerror: data type 'category' not understood
SQL Server manager studio(SSMS)安装教程
My seven years with NLP
同事上了个厕所,我帮产品妹子轻松完成BI数据产品顺便得到奶茶奖励
Reflex WMS中阶系列3:显示已发货可换组
A method to measure the similarity of time series: from Euclidean distance to DTW and its variants
How to translate professional papers and write English abstracts better
简单描述 MySQL 中,索引,主键,唯一索引,联合索引 的区别,对数据库的性能有什么影响(从读写两方面)
SSO process analysis
SSO流程分析
How to do a good job in financial literature translation?
P5706 [deep foundation 2. Example 8] redistributing fat house water -- February 13, 2022