【Dream的刷題樂園】️LeetCode每日遊園系列️——503. 下一個更大元素 II 單調棧園

是Dream呀 2021-08-15 13:46:31 阅读数:863

本文一共[544]字,预计阅读时长:1分钟~
dream leetcode 每日 系列 下一


在這裏插入圖片描述


Hello,大家好我是Dream,歡迎大家來到刷題樂園
遊園須知: 本樂園從不缺乏天才,努力才是你的最終入場券!
導遊主要使用Python語言,同時歡迎其他語言的小夥伴進來玩耍️️️
遊園過程中,如果發現有錯誤的話,歡迎大家評論區及時斧正️️️
最後,祝大家遊園愉快,一起加油進步

樂園描述

給定一個循環數組(最後一個元素的下一個元素是數組的第一個元素),輸出每個元素的下一個更大元素。數字 x 的下一個更大的元素是按數組遍曆順序,這個數字之後的第一個比它更大的數,這意味著你應該循環地搜索它的下一個更大的數。如果不存在,則輸出 -1。

示例 1:
輸入: [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數是 2;
數字 2 找不到下一個更大的數;
第二個 1 的下一個最大的數需要循環搜索,結果也是 2。
注意: 輸入數組的長度不會超過 10000

遊園准備

今天遊玩的兩個重點:

  • 如何求下一個更大的元素
  • 如何實現循環數組

️‍錯誤遊玩:本題如果暴力求解,對於每個元素都向後去尋找比它更大的元素,那麼時間複雜度 O(N^2) 會超時。必須想辦法優化。

️‍正確遊玩:根據上面的分析可知,可以遍曆一次數組,如果元素是單調遞减的(則他們的「下一個更大元素」相同),我們就把這些元素保存,直到找到一個較大的元素;把該較大元素逐一跟保存了的元素比較,如果該元素更大,那麼它就是前面元素的「下一個更大元素」。

️在實現上,我們可以使用「單調棧」來實現,單調棧是說棧裏面的元素從棧底到棧頂是單調遞增或者單調遞减的(類似於漢諾塔)

️棧的相關操作如下:

  • Stack() 創建一個空的新棧。 它不需要參數,並返回一個空棧。
  • push(item)將一個新項添加到棧的頂部。它需要 item 做參數並不返回任何內容。
  • pop() 從棧中删除頂部項。它不需要參數並返回 item 。棧被修改。
  • peek() 從棧返回頂部項,但不會删除它。不需要參數。 不修改棧。
  • isEmpty() 測試棧是否為空。不需要參數,並返回布爾值。
  • size() 返回棧中的 item 數量。不需要參數,並返回一個整數。

開始遊玩

我們使用單調棧時,保存的是元素對應的下標。而這個單調棧是 單調不昇,即是棧底到棧頂中存儲下標對應的元素值是單調遞减的。下面是具體的思路:
聲明單調棧 stack,開始遍曆數組;
當棧非空時,直接將遍曆元素對應的下標壓入棧中;
當棧為空時,需要比較棧頂下標對應元素值與當前元素值的大小:

  • 若棧頂下標對應元素值 當前元素值時,彈出棧頂下標,根據下標在結果列錶中找到對應的元素,其下一個更大的元素則為當前元素。(這裏需要循環比較判斷,直到棧頂下標對應的元素值大於當前元素停止)
  • 若棧頂下標對應元素值 ≥ 當前元素值時,只需要將當前元素對應的下標壓入棧中,不做其他處理。
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [-1] * n
stack = []
# 遍曆
for i in range(2 * n - 1):
# 棧非空,出棧比較棧頂索引對應元素值與當前元素值的大小
while stack and nums[stack[-1]] < nums[i % n]:
res[stack.pop()] = nums[i % n]
# 壓入棧中的是元素的索引
# 這裏用取模的方法映射索引到原數組中
stack.append(i % n)
return res

在這裏插入圖片描述

遊玩總結

The stage extends as far as the heart goes~加油!️️️

最後一點小福利帶給大家:如果想快速上手python的小夥伴們,這個詳細整理PPT可以迅速幫助大家打牢python基礎,需要的小夥伴們可以下載一下Python入門基礎教程全套+小白速成+學不會來找我!

好啦,這就是今天要給大家分享的全部內容了
️️️如果你喜歡的話,就不要吝惜你的一鍵三連了~在這裏插入圖片描述

版权声明:本文为[是Dream呀]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815134615060B.html