付費限定

用 單調棧 來解 每日溫度變化 Daily Temperatures Leetcode #739 精選75題

更新於 發佈於 閱讀時間約 5 分鐘

題目敘述

題目會給定一個輸入陣列temperatures ,分別代表每一天的溫度。

請計算每一天還要再過幾天才會遇到更溫暖的日子,如果遇不到,則回填0

請以陣列的形式返回答案。


題目的原文敘述


測試範例

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

約束條件

Constraints:

  • 1 <= temperatures.length <= 10^5

溫度陣列的長度介於 1 ~ 十萬。

  • 30 <= temperatures[i] <= 100

每個陣列元素值介於30~100之間。


演算法 Monotone Stack 單調棧


維護一個遞減單調棧,每次推入溫度時,把前面比較小的溫度都pop出來,並且趁機計算兩者之間的索引差值,更新前面比較冷的那幾天再過幾天才會遇到更溫暖的日子。最後推入自己當下這天的索引值。

反覆迭代更新,掃描每一天的溫度,同時維護遞減單調棧。

如果某一天無解,也就是某一天之後不會遇到更溫暖的日子,則回填0。


程式碼 Monotone Stack 單調棧

class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

size = len(temperatures)

# waiting days of next warmer temperature
waiting_days = [ 0 for _ in range(size) ]

## monotone decreasing stack to help us to find waiting days of next warmer temperature
# first parameter is array index
# second parameter is temperature
stack = []

for cur_idx, cur_t in enumerate(temperatures):

# keep stack in decreasing order
while stack and cur_t > stack[-1][1]:

# get index and temperature of previous colder day
prev_idx, prev_t = stack.pop()

# update waiting days for previous colder day
waiting_days[prev_idx] = cur_idx - prev_idx

# add current index and current temperature into stack
stack.append( (cur_idx, cur_t) )


return waiting_days
以行動支持創作者!付費即可解鎖
本篇內容共 2006 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
avatar-img
95會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言1
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/05/29
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中)提及了這篇文章,趕快過去看看吧!
題目敘述 給定兩個字串word1和word2,每次操作時,可以有三個選項 插入一個字元 刪除一個字元 替換一個字元 請問把word1轉換成word2的最小操作次數是多少? 題目的原文敘述 約束條件 Constraints: 0 <= word1.length, word2.le
題目敘述 題目會給我們兩種無限量供應的骨牌Domino 和 Tromino,形狀分別如下 題目的輸入會有一個參數n。 可以任意旋轉方向進行拼接,請問最後拼成 2 x n 長方形區域的方法數有幾種? 例如 n = 3 時,拼成2 x 3 的長方形區域有五種方法。 題目的原文敘述
題目敘述 題目會給我們一個大樓陣列heights,裡面分別記錄每一棟大樓的高度。還有參數bricks代表可用的磚塊數目,和 ladders代表可用的伸縮爬梯數目。 一開始從最左邊的大樓頂樓開始出發。 假如下一棟比現在這棟大樓還矮,或者一樣高,則我們可以直接抵達下一棟。 假如下一棟比現在
題目敘述 題目會給我們一個陣列prices,裡面的數值代表每一個交易日的股票股價。 每次買入股票時會有一個額外附帶的交易成本fee。 題目讓我們做多,而且不限制交易次數。 題目禁止持有多重部位,也就是說,必須是買賣輪流交替的形式。 比如說 買,買,買 這種方式是不被允許的。 請問最終
題目敘述 題目會給我們泰伯納西數列的一般項和初始條件,要求我們實現找出第n項的function。 def tribonacci(self, n: int): 泰伯納西數列的一般項: Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. 泰伯納西數列的初始條件: T0 = 0,
題目敘述 題目會給我們一個輸入整數陣列arr,和一個初始化的刪除次數k? 我們可以任意選擇從arr中刪除k個陣列元素,請問最後留下來的數字,最少會有幾個不同的數字? 註: 最後不同的數字越少越好。 題目的原文敘述 測試範例 Example 1: Input: arr = [5,5
題目敘述 給定兩個字串word1和word2,每次操作時,可以有三個選項 插入一個字元 刪除一個字元 替換一個字元 請問把word1轉換成word2的最小操作次數是多少? 題目的原文敘述 約束條件 Constraints: 0 <= word1.length, word2.le
題目敘述 題目會給我們兩種無限量供應的骨牌Domino 和 Tromino,形狀分別如下 題目的輸入會有一個參數n。 可以任意旋轉方向進行拼接,請問最後拼成 2 x n 長方形區域的方法數有幾種? 例如 n = 3 時,拼成2 x 3 的長方形區域有五種方法。 題目的原文敘述
題目敘述 題目會給我們一個大樓陣列heights,裡面分別記錄每一棟大樓的高度。還有參數bricks代表可用的磚塊數目,和 ladders代表可用的伸縮爬梯數目。 一開始從最左邊的大樓頂樓開始出發。 假如下一棟比現在這棟大樓還矮,或者一樣高,則我們可以直接抵達下一棟。 假如下一棟比現在
題目敘述 題目會給我們一個陣列prices,裡面的數值代表每一個交易日的股票股價。 每次買入股票時會有一個額外附帶的交易成本fee。 題目讓我們做多,而且不限制交易次數。 題目禁止持有多重部位,也就是說,必須是買賣輪流交替的形式。 比如說 買,買,買 這種方式是不被允許的。 請問最終
題目敘述 題目會給我們泰伯納西數列的一般項和初始條件,要求我們實現找出第n項的function。 def tribonacci(self, n: int): 泰伯納西數列的一般項: Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. 泰伯納西數列的初始條件: T0 = 0,
題目敘述 題目會給我們一個輸入整數陣列arr,和一個初始化的刪除次數k? 我們可以任意選擇從arr中刪除k個陣列元素,請問最後留下來的數字,最少會有幾個不同的數字? 註: 最後不同的數字越少越好。 題目的原文敘述 測試範例 Example 1: Input: arr = [5,5
你可能也想看
Google News 追蹤
Thumbnail
本文以戀愛為比喻,深入淺出地探討投資哲學,提醒讀者投資需理性評估,不可盲目跟風,並強調投資自己才是最穩健的選擇。
2025/01/16 市場消息解讀:COWOS 訂單調整的影響與背景分析 COWOS 訂單調整的真相 近期市場傳出 NVIDIA 調整 COWOS 訂單的消息,但需要具體分析這一訂單背後的意涵。目前的調整應主要針對 COWOS S,且描述為“砍單”可能並不完全準確。調整的實質是 COWOS S
Thumbnail
今天節氣交小暑,代表著天氣非常炎熱的開始...
最近天氣炎熱 平日上班都有冷氣吹 假日出門 不論是大眾運輸和店家也都有冷氣
Thumbnail
李明是一個敏感而內向的年輕人,他一直害怕付出真心去愛一個人。他曾經經歷過一段痛苦的感情,對方在他毫無防備的時候突然消失,讓他陷入了深深的孤獨和傷痛之中。   然而,命運似乎總是喜歡和他開玩笑。在一次偶然的機會裡,李明遇到了一位叫林婷的女孩。她溫柔善良、聰明伶俐,兩人很快就成為了好朋友。隨
Thumbnail
題目敘述 題目會給我們一個StockSpanner類別, 還有對應的建構子和function: int next( int price)介面。 next(int price)呼叫的時後回傳入當天的股票價格,要求我們計算price這個價格是過去k天以來的最高價,返回k值。 舉例來說: 若股價分
Thumbnail
本文以戀愛為比喻,深入淺出地探討投資哲學,提醒讀者投資需理性評估,不可盲目跟風,並強調投資自己才是最穩健的選擇。
2025/01/16 市場消息解讀:COWOS 訂單調整的影響與背景分析 COWOS 訂單調整的真相 近期市場傳出 NVIDIA 調整 COWOS 訂單的消息,但需要具體分析這一訂單背後的意涵。目前的調整應主要針對 COWOS S,且描述為“砍單”可能並不完全準確。調整的實質是 COWOS S
Thumbnail
今天節氣交小暑,代表著天氣非常炎熱的開始...
最近天氣炎熱 平日上班都有冷氣吹 假日出門 不論是大眾運輸和店家也都有冷氣
Thumbnail
李明是一個敏感而內向的年輕人,他一直害怕付出真心去愛一個人。他曾經經歷過一段痛苦的感情,對方在他毫無防備的時候突然消失,讓他陷入了深深的孤獨和傷痛之中。   然而,命運似乎總是喜歡和他開玩笑。在一次偶然的機會裡,李明遇到了一位叫林婷的女孩。她溫柔善良、聰明伶俐,兩人很快就成為了好朋友。隨
Thumbnail
題目敘述 題目會給我們一個StockSpanner類別, 還有對應的建構子和function: int next( int price)介面。 next(int price)呼叫的時後回傳入當天的股票價格,要求我們計算price這個價格是過去k天以來的最高價,返回k值。 舉例來說: 若股價分