LeetCode 739 Daily Temperatures 題解單調棧求解下一個更大元素距離【免費下載鏈接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode題解記錄自己的leetcode解題之路。)項目地址: https://gitcode.com/gh_mirrors/le/leetcode導讀本文圍繞 LeetCode 739「每日溫度Daily Temperatures」展開這是 leetcode 題解倉庫「每日一題」系列活動在 2019-06-06 收錄的經典題目對應源碼位于 daily/answers/739.daily-temperatures.js。題目要求對每一天的溫度計算需要等待多少天才能出現(xiàn)更高的溫度本質是數(shù)組中每個元素之后第一個更大元素的距離問題。讀完本文你將掌握兩種解法O(n2) 暴力雙層循環(huán)與 O(n) 單調遞減棧并理解單調棧這一算法范式如何在 42. 接雨水、84. 柱狀圖中最大的矩形 等同類問題中復用。一、信息卡片與題目背景該題在每日一題中的基礎信息如下時間2019-06-06題目739. Daily TemperaturestagArrayStack倉庫的 daily/README.md 中記錄了每日一題的歷史匯總其中第 739 題的條目為tag: Array Stack與本題核心算法數(shù)組 棧完全對應。每日一題是倉庫作者在交流群中發(fā)起的共解一道題的活動題目被記錄后會篩選進入題解模塊因此本文所講解的解法與倉庫 problems 目錄下的正式題解同源同質。二、題目描述與約束分析原題描述如下Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.示例輸入輸出T [73, 74, 75, 71, 69, 72, 76, 73] 輸出 [1, 1, 4, 2, 1, 1, 0, 0]約束條件溫度列表長度范圍[1, 30000]每個溫度取值[30, 100]。題意拆解對于下標i需要找到最小的j i使得T[j] T[i]答案記為j - i若不存在這樣的j答案記為0。例如T[2] 75之后第一個大于 75 的是下標 6 的 76等待天數(shù)為6 - 2 4。需要特別注意的是等值不算更暖只有嚴格大于才滿足條件這一細節(jié)在編寫比較條件時容易出錯也是兩種解法的核心比較符。三、解法一暴力雙層循環(huán)O(n2)3.1 思路最簡單直觀的做法外層循環(huán)枚舉當天T[i]內層循環(huán)枚舉當天之后的每一天T[j]j從i1開始一旦找到第一個滿足T[j] T[i]的j則result[i] j - i并跳出內層循環(huán)若內層循環(huán)結束仍未找到result[i]保持0。原文檔給出的 JavaScript 實現(xiàn)/** * param {number[]} T * return {number[]} * 雙層for循環(huán) */ var dailyTemperatures function(T) { let result []; for(let i 0; i T.length; i) { result[i] 0; for(let j i 1; j T.length; j) { if (T[i] T[j]) { result[i] j - i; break; } } } return result; };3.2 復雜度與缺陷時間復雜度O(n2)。最壞情況下如溫度嚴格遞減[100, 99, 98, ...]每個i都要遍歷完其后所有元素空間復雜度O(1)除結果數(shù)組外無額外空間。原文檔對該解法的評價是效率很低這在 n 最大達 30000 時尤其明顯——最壞約 9 億次比較在 LeetCode 上大概率超時。暴力解法價值在于幫助理解題意作為優(yōu)化解的對照基準。四、解法二單調遞減棧O(n)4.1 核心思想棧中存下標優(yōu)化思路是用空間換時間維護一個棧棧內保存的是尚未找到下一個更高溫度的下標。關鍵技巧在于棧中存下標而非溫度值因為答案要求天數(shù)差j - i存下標才能同時取出溫度T[下標]和計算距離。維護單調性從棧底到棧頂下標對應的溫度單調遞減即棧頂是當前已掃描溫度中最低的待處理下標。這正是 thinkings/monotone-stack.md 中定義的單調遞減棧以出棧順序看被彈出的元素按溫度遞減排列。4.2 算法步驟初始化空棧stack和結果數(shù)組result初始全部為 0從左到右for遍歷數(shù)組當前下標為i若棧非空且T[stack 棧頂] T[i]說明當前溫度T[i]就是棧頂下標之后第一個更高的溫度于是彈出棧頂peek令result[peek] i - peek重復上一步直到?？栈驐ｍ敎囟炔恍∮赥[i]保持單調遞減將i入棧遍歷結束后棧中剩余的下標都是其后不存在更高溫度的天其result保持初始值0。原文檔給出的 JavaScript 實現(xiàn)/** * param {number[]} T * return {number[]} * 遞減棧 */ var dailyTemperatures function(T) { let stack []; let result []; for (let i 0; i T.length; i) { result[i] 0; while(stack.length 0 T[stack[stack.length - 1]] T[i]) { let peek stack.pop(); result[peek] i - peek; } stack.push(i); } return result; };Python3 實現(xiàn)class Solution: def dailyTemperatures(self, T: List[int]) - List[int]: stack [] ans [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: peek stack.pop(-1) ans[peek] i - peek stack.append(i) return ans4.3 逐步推演示例以T [73, 74, 75, 71, 69, 72, 76, 73]為例iT[i]操作棧存下標結果變化073入棧[0]result 全 0174T[0]73 74彈出 0result[0]1-01入棧 1[1]result[0]1275T[1]74 75彈出 1result[1]1入棧 2[2]result[1]137171 不大于 75直接入棧[2,3]-46969 不大于 71直接入棧[2,3,4]-572T[4]69 72彈出 4result[4]1T[3]71 72彈出 3result[3]2入棧 5[2,5]result[4]1, result[3]2676T[5]72 76彈出 5result[5]1T[2]75 76彈出 2result[2]4入棧 6[6]result[5]1, result[2]477373 不大于 76入棧[6,7]-最終result [1, 1, 4, 2, 1, 1, 0, 0]與題目示例一致?？梢钥吹揭粋€暖鋒如 76經過時會把棧中所有比它冷的天一次性結算掉這正是單調棧高效的本質。4.4 復雜度分析時間復雜度O(n)。每個下標最多入棧一次、出棧一次均攤 O(1)總代價線性空間復雜度O(n)。棧最多同時容納 n 個下標例如溫度嚴格遞減時。倉庫答案文件 daily/answers/739.daily-temperatures.js 同時保留了兩種解法的實現(xiàn)暴力版本被注釋保留作為對比正式采用單調棧版本并標注了典型的空間換時間——這與本文的復雜度結論完全一致可作為源碼級佐證。五、舉一反三單調棧通用模板739. Daily Temperatures是 thinkings/monotone-stack.md 專題文章明確引用的代表題目見其題目推薦一節(jié)。該專題總結了如下通用模板核心一句話是如果壓棧之后仍然可以保持單調性直接壓否則先彈出棧內元素直到壓入后可以保持單調性。Python 模板class Solution: def monostoneStack(self, arr: List[int]) - List[int]: stack [] ans [0] * len(arr) # 初始值根據題意調整可能是 -1 或 0 for i in range(len(arr)): while stack and arr[i] arr[stack[-1]]: peek stack.pop() ans[peek] i - peek stack.append(i) return ansJavaScript 模板var monostoneStack function (T) { let stack []; let result []; for (let i 0; i T.length; i) { result[i] 0; while (stack.length 0 T[stack[stack.length - 1]] T[i]) { let peek stack.pop(); result[peek] i - peek; } stack.push(i); } return result; };5.1 模板的三個可調點比較符號求解下一個更大元素用arr[i] arr[棧頂]求解下一個更小元素則反向。本題是找更高溫度故用Python 中對應T[i] T[stack[-1]]答案賦值本題存天數(shù)差i - peek若題目要求存值如下一個更大元素的值則改為ans[peek] arr[i]初始值本題不存在更高溫度時填 0若題目要求不存在時填 -1則初始化數(shù)組為 -1與 thinkings/monotone-stack.md 偽代碼一致。5.2 邊界與哨兵法原文檔與單調棧專題均提醒遍歷結束后棧中殘留的下標沒有下一個更大元素。若題目需要利用到數(shù)組的全部信息容易因忽略邊界而漏解。專題推薦哨兵法在原數(shù)組右側追加一個足夠小的值如 -1強制在遍歷末尾把所有剩余元素彈出結算從而簡化代碼邏輯。本題中殘留元素答案天然為 0無需額外處理但理解這一技巧有助于應對其他變體。六、單調棧相關題目推薦掌握了 739 的單調棧解法后可以在倉庫中繼續(xù)挑戰(zhàn)以下同族題目它們都依賴下一個更大/更小元素這一核心場景42. 接雨水其前置知識明確列出單調棧屬于難度較大的應用84. 柱狀圖中最大的矩形同樣以單調棧為前置知識尋找左右邊界1019. 鏈表中的下一個更大節(jié)點把數(shù)組換成鏈表思路與本題高度同構其題解原文明確指出看完題目就應該想到單調棧thinkings/monotone-stack.md 還推薦了 316. 去除重復字母、402. 移掉 K 位數(shù)字、496. 下一個更大元素 I、581. 最短無序連續(xù)子數(shù)組、901. 股票價格跨度等題目。七、總結LeetCode 739「每日溫度」是單調棧算法最典型的入門題之一暴力解雙層循環(huán)O(n2)思路簡單適合理解題意但在 n30000 的約束下不可行單調遞減棧O(n)用棧存下標、按溫度單調的方式讓每個元素只進出棧一次以 O(n) 空間換取 O(n) 時間解題關鍵三要素棧中存下標而非值、比較用嚴格大于等溫不算更暖、殘留棧元素的答案保持為0該題與倉庫 thinkings/monotone-stack.md 專題、daily/answers/739.daily-temperatures.js 源碼相互印證可作為學習下一個更大元素問題族的最佳起點后續(xù)可平滑過渡到接雨水、柱狀圖最大矩形、鏈表下一個更大節(jié)點等進階題目。【免費下載鏈接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode題解記錄自己的leetcode解題之路。)項目地址: https://gitcode.com/gh_mirrors/le/leetcode創(chuàng)作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考 LeetCode 739 Daily Temperatures 題解：單調棧求解“下一個更大元素“距離
LeetCode 739 Daily Temperatures 題解單調棧求解下一個更大元素距離【免費下載鏈接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode題解記錄自己的leetcode解題之路。)項目地址: https://gitcode.com/gh_mirrors/le/leetcode導讀本文圍繞 LeetCode 739「每日溫度Daily Temperatures」展開這是 leetcode 題解倉庫「每日一題」系列活動在 2019-06-06 收錄的經典題目對應源碼位于 daily/answers/739.daily-temperatures.js。題目要求對每一天的溫度計算需要等待多少天才能出現(xiàn)更高的溫度本質是數(shù)組中每個元素之后第一個更大元素的距離問題。讀完本文你將掌握兩種解法O(n2) 暴力雙層循環(huán)與 O(n) 單調遞減棧并理解單調棧這一算法范式如何在 42. 接雨水、84. 柱狀圖中最大的矩形 等同類問題中復用。一、信息卡片與題目背景該題在每日一題中的基礎信息如下時間2019-06-06題目739. Daily TemperaturestagArrayStack倉庫的 daily/README.md 中記錄了每日一題的歷史匯總其中第 739 題的條目為tag: Array Stack與本題核心算法數(shù)組 棧完全對應。每日一題是倉庫作者在交流群中發(fā)起的共解一道題的活動題目被記錄后會篩選進入題解模塊因此本文所講解的解法與倉庫 problems 目錄下的正式題解同源同質。二、題目描述與約束分析原題描述如下Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.示例輸入輸出T [73, 74, 75, 71, 69, 72, 76, 73] 輸出 [1, 1, 4, 2, 1, 1, 0, 0]約束條件溫度列表長度范圍[1, 30000]每個溫度取值[30, 100]。題意拆解對于下標i需要找到最小的j i使得T[j] T[i]答案記為j - i若不存在這樣的j答案記為0。例如T[2] 75之后第一個大于 75 的是下標 6 的 76等待天數(shù)為6 - 2 4。需要特別注意的是等值不算更暖只有嚴格大于才滿足條件這一細節(jié)在編寫比較條件時容易出錯也是兩種解法的核心比較符。三、解法一暴力雙層循環(huán)O(n2)3.1 思路最簡單直觀的做法外層循環(huán)枚舉當天T[i]內層循環(huán)枚舉當天之后的每一天T[j]j從i1開始一旦找到第一個滿足T[j] T[i]的j則result[i] j - i并跳出內層循環(huán)若內層循環(huán)結束仍未找到result[i]保持0。原文檔給出的 JavaScript 實現(xiàn)/** * param {number[]} T * return {number[]} * 雙層for循環(huán) */ var dailyTemperatures function(T) { let result []; for(let i 0; i T.length; i) { result[i] 0; for(let j i 1; j T.length; j) { if (T[i] T[j]) { result[i] j - i; break; } } } return result; };3.2 復雜度與缺陷時間復雜度O(n2)。最壞情況下如溫度嚴格遞減[100, 99, 98, ...]每個i都要遍歷完其后所有元素空間復雜度O(1)除結果數(shù)組外無額外空間。原文檔對該解法的評價是效率很低這在 n 最大達 30000 時尤其明顯——最壞約 9 億次比較在 LeetCode 上大概率超時。暴力解法價值在于幫助理解題意作為優(yōu)化解的對照基準。四、解法二單調遞減棧O(n)4.1 核心思想棧中存下標優(yōu)化思路是用空間換時間維護一個棧棧內保存的是尚未找到下一個更高溫度的下標。關鍵技巧在于棧中存下標而非溫度值因為答案要求天數(shù)差j - i存下標才能同時取出溫度T[下標]和計算距離。維護單調性從棧底到棧頂下標對應的溫度單調遞減即棧頂是當前已掃描溫度中最低的待處理下標。這正是 thinkings/monotone-stack.md 中定義的單調遞減棧以出棧順序看被彈出的元素按溫度遞減排列。4.2 算法步驟初始化空棧stack和結果數(shù)組result初始全部為 0從左到右for遍歷數(shù)組當前下標為i若棧非空且T[stack 棧頂] T[i]說明當前溫度T[i]就是棧頂下標之后第一個更高的溫度于是彈出棧頂peek令result[peek] i - peek重復上一步直到?？栈驐ｍ敎囟炔恍∮赥[i]保持單調遞減將i入棧遍歷結束后棧中剩余的下標都是其后不存在更高溫度的天其result保持初始值0。原文檔給出的 JavaScript 實現(xiàn)/** * param {number[]} T * return {number[]} * 遞減棧 */ var dailyTemperatures function(T) { let stack []; let result []; for (let i 0; i T.length; i) { result[i] 0; while(stack.length 0 T[stack[stack.length - 1]] T[i]) { let peek stack.pop(); result[peek] i - peek; } stack.push(i); } return result; };Python3 實現(xiàn)class Solution: def dailyTemperatures(self, T: List[int]) - List[int]: stack [] ans [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: peek stack.pop(-1) ans[peek] i - peek stack.append(i) return ans4.3 逐步推演示例以T [73, 74, 75, 71, 69, 72, 76, 73]為例iT[i]操作棧存下標結果變化073入棧[0]result 全 0174T[0]73 74彈出 0result[0]1-01入棧 1[1]result[0]1275T[1]74 75彈出 1result[1]1入棧 2[2]result[1]137171 不大于 75直接入棧[2,3]-46969 不大于 71直接入棧[2,3,4]-572T[4]69 72彈出 4result[4]1T[3]71 72彈出 3result[3]2入棧 5[2,5]result[4]1, result[3]2676T[5]72 76彈出 5result[5]1T[2]75 76彈出 2result[2]4入棧 6[6]result[5]1, result[2]477373 不大于 76入棧[6,7]-最終result [1, 1, 4, 2, 1, 1, 0, 0]與題目示例一致?？梢钥吹揭粋€暖鋒如 76經過時會把棧中所有比它冷的天一次性結算掉這正是單調棧高效的本質。4.4 復雜度分析時間復雜度O(n)。每個下標最多入棧一次、出棧一次均攤 O(1)總代價線性空間復雜度O(n)。棧最多同時容納 n 個下標例如溫度嚴格遞減時。倉庫答案文件 daily/answers/739.daily-temperatures.js 同時保留了兩種解法的實現(xiàn)暴力版本被注釋保留作為對比正式采用單調棧版本并標注了典型的空間換時間——這與本文的復雜度結論完全一致可作為源碼級佐證。五、舉一反三單調棧通用模板739. Daily Temperatures是 thinkings/monotone-stack.md 專題文章明確引用的代表題目見其題目推薦一節(jié)。該專題總結了如下通用模板核心一句話是如果壓棧之后仍然可以保持單調性直接壓否則先彈出棧內元素直到壓入后可以保持單調性。Python 模板class Solution: def monostoneStack(self, arr: List[int]) - List[int]: stack [] ans [0] * len(arr) # 初始值根據題意調整可能是 -1 或 0 for i in range(len(arr)): while stack and arr[i] arr[stack[-1]]: peek stack.pop() ans[peek] i - peek stack.append(i) return ansJavaScript 模板var monostoneStack function (T) { let stack []; let result []; for (let i 0; i T.length; i) { result[i] 0; while (stack.length 0 T[stack[stack.length - 1]] T[i]) { let peek stack.pop(); result[peek] i - peek; } stack.push(i); } return result; };5.1 模板的三個可調點比較符號求解下一個更大元素用arr[i] arr[棧頂]求解下一個更小元素則反向。本題是找更高溫度故用Python 中對應T[i] T[stack[-1]]答案賦值本題存天數(shù)差i - peek若題目要求存值如下一個更大元素的值則改為ans[peek] arr[i]初始值本題不存在更高溫度時填 0若題目要求不存在時填 -1則初始化數(shù)組為 -1與 thinkings/monotone-stack.md 偽代碼一致。5.2 邊界與哨兵法原文檔與單調棧專題均提醒遍歷結束后棧中殘留的下標沒有下一個更大元素。若題目需要利用到數(shù)組的全部信息容易因忽略邊界而漏解。專題推薦哨兵法在原數(shù)組右側追加一個足夠小的值如 -1強制在遍歷末尾把所有剩余元素彈出結算從而簡化代碼邏輯。本題中殘留元素答案天然為 0無需額外處理但理解這一技巧有助于應對其他變體。六、單調棧相關題目推薦掌握了 739 的單調棧解法后可以在倉庫中繼續(xù)挑戰(zhàn)以下同族題目它們都依賴下一個更大/更小元素這一核心場景42. 接雨水其前置知識明確列出單調棧屬于難度較大的應用84. 柱狀圖中最大的矩形同樣以單調棧為前置知識尋找左右邊界1019. 鏈表中的下一個更大節(jié)點把數(shù)組換成鏈表思路與本題高度同構其題解原文明確指出看完題目就應該想到單調棧thinkings/monotone-stack.md 還推薦了 316. 去除重復字母、402. 移掉 K 位數(shù)字、496. 下一個更大元素 I、581. 最短無序連續(xù)子數(shù)組、901. 股票價格跨度等題目。七、總結LeetCode 739「每日溫度」是單調棧算法最典型的入門題之一暴力解雙層循環(huán)O(n2)思路簡單適合理解題意但在 n30000 的約束下不可行單調遞減棧O(n)用棧存下標、按溫度單調的方式讓每個元素只進出棧一次以 O(n) 空間換取 O(n) 時間解題關鍵三要素棧中存下標而非值、比較用嚴格大于等溫不算更暖、殘留棧元素的答案保持為0該題與倉庫 thinkings/monotone-stack.md 專題、daily/answers/739.daily-temperatures.js 源碼相互印證可作為學習下一個更大元素問題族的最佳起點后續(xù)可平滑過渡到接雨水、柱狀圖最大矩形、鏈表下一個更大節(jié)點等進階題目。【免費下載鏈接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode題解記錄自己的leetcode解題之路。)項目地址: https://gitcode.com/gh_mirrors/le/leetcode創(chuàng)作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考