当前位置:网站首页>【Hot100】739. 每日溫度
【Hot100】739. 每日溫度
2022-07-06 06:50:00 【王六六的IT日常】
739. 每日溫度
給定一個整數數組 temperatures ,錶示每天的溫度,返回一個數組 answer ,其中 answer[i] 是指對於第 i 天,下一個更高溫度出現在幾天後。如果氣溫在這之後都不會昇高,請在該比特置用 0 來代替。
輸入: temperatures = [73,74,75,71,69,72,76,73]
輸出: [1,1,4,2,1,1,0,0]
題目理解:
對於輸入 73,它需要 經過一天 才能等到溫度的昇高,也就是在第二天的時候,溫度昇高到 74 ,所以對應的結果是 1。
對於輸入 74,它需要 經過一天 才能等到溫度的昇高,也就是在第三天的時候,溫度昇高到 75 ,所以對應的結果是 1。
對於輸入 75,它經過 1 天後發現溫度是 71,沒有超過它,繼續等,一直 等了四天,在第七天才等到溫度的昇高,溫度昇高到 76 ,所以對應的結果是 4 。
對於輸入 71,它經過 1 天後發現溫度是 69,沒有超過它,繼續等,一直 等了兩天,在第六天才等到溫度的昇高,溫度昇高到 72 ,所以對應的結果是 2 。
對於輸入 69,它 經過一天 後發現溫度是 72,已經超過它,所以對應的結果是 1 。
對於輸入 72,它 經過一天 後發現溫度是 76,已經超過它,所以對應的結果是 1 。
對於輸入 76,後續 沒有溫度 可以超過它,所以對應的結果是 0 。
對於輸入 73,後續 沒有溫度 可以超過它,所以對應的結果是 0 。
想法:針對每個溫度值 向後進行依次搜索 ,找到比當前溫度更高的值,這是最容易想到的辦法。
原理:是從左到右除了最後一個數其他所有的數都遍曆一次,最後一個數據對應的結果肯定是 0,就不需要計算。
遍曆的時候,每個數都去向後數,直到找到比它大的數,數的次數就是對應輸出的值。
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;
}
}
用棧來解决:
遞减棧 :棧裏只有遞减元素。
遍曆整個數組,如果棧不空,且當前數字大於棧頂元素,那麼如果直接入棧的話就不是 遞减棧 ,所以需要取出棧頂元素,由於當前數字大於棧頂元素的數字,而且一定是第一個大於棧頂元素的數,直接求出下標差就是二者的距離。
繼續看新的棧頂元素,直到當前數字小於等於棧頂元素停止,然後將數字入棧,這樣就可以一直保持遞减棧,且每個數字和第一個大於它的數的距離也可以算出來。
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;
}
}
边栏推荐
- 云上有AI,让地球科学研究更省力
- 金融德语翻译,北京专业的翻译公司
- Reflex WMS medium level series 3: display shipped replaceable groups
- Lesson 7 tensorflow realizes convolutional neural network
- Practical guidance for interface automation testing (Part I): what preparations should be made for interface automation
- Market segmentation of supermarket customers based on purchase behavior data (RFM model)
- 18.多级页表与快表
- Leetcode daily question (971. flip binary tree to match preorder traversal)
- Reflex WMS中阶系列3:显示已发货可换组
- 成功解决AttributeError: Can only use .cat accessor with a ‘category‘ dtype
猜你喜欢
After working for 10 years, I changed to a programmer. Now I'm 35 + years old and I'm not anxious
What is the difference between int (1) and int (10)? Senior developers can't tell!
Fedora/rehl installation semanage
Fedora/REHL 安装 semanage
Pallet management in SAP SD delivery process
生物医学本地化翻译服务
Map of mL: Based on the adult census income two classification prediction data set (whether the predicted annual income exceeds 50K), use the map value to realize the interpretable case of xgboost mod
Biomedical English contract translation, characteristics of Vocabulary Translation
Biomedical localization translation services
[ 英語 ] 語法重塑 之 動詞分類 —— 英語兔學習筆記(2)
随机推荐
Suspended else
How to convert flv file to MP4 file? A simple solution
Tms320c665x + Xilinx artix7 DSP + FPGA high speed core board
成功解决TypeError: data type ‘category‘ not understood
自动化测试环境配置
Financial German translation, a professional translation company in Beijing
Day 239/300 注册密码长度为8~14个字母数字以及标点符号至少包含2种校验
《从0到1:CTFer成长之路》书籍配套题目(周更)
成功解决AttributeError: Can only use .cat accessor with a ‘category‘ dtype
【刷题】怎么样才能正确的迎接面试?
Simple use of MySQL database: add, delete, modify and query
SQL Server manager studio(SSMS)安装教程
Windows Server 2016 standard installing Oracle
Day 246/300 ssh连接提示“REMOTE HOST IDENTIFICATION HAS CHANGED! ”
接口自动化测试实践指导(上):接口自动化需要做哪些准备工作
GET 和 POST 请求类型的区别
Cobalt strike feature modification
Distributed system basic (V) protocol (I)
(practice C language every day) reverse linked list II
mysql的基础命令