「@Author：Runsen」

? 編程的本質來源于算法，而算法的本質來源于數學，編程只不過將數學題進行代碼化。 「---- Runsen」
?

據說，放張小姐姐覺得照片可以提高閱讀量，圖是來源學校的2020新生。

算法，一門既不容易入門，也不容易精通的學問。

最近看了 labuladong的文章：單調棧解題模板秒殺三道算法題。

根據腦海大綱的思路，發現這是一個非常重要的題型，于是我趕緊花費點時間刷了下。

單調棧

單調棧的實質是有單調性的棧，包括單調遞增棧和單調遞減棧。通過棧的入棧和出棧維護一個動態的滑動窗口，然后棧頂元素是該窗口的最大值或最小值，通過一次遍歷，就可以計算出所有元素的下一個較大值或較小值。

如下圖，分別插入6,10,3,7,4,12的時候，單調遞增棧和單調遞減棧的情況：

下一個更大元素

給一個int組成的array，找到下一個比當前值更大的元素組成的數組，如果找不到，填充-1，例子：nums = [44 ,15 ,22, 9 ,7, 2 ,18 ,23, 27 ]輸出：[-1, 22, 23, 18, 18, 18, 23, 27, -1]

最簡單的思路就是兩重循環，第二次循環從當前位置往后掃，直到掃到一個比它大的數。時間復雜度。

res = [] nums = [44 ,15 ,22, 9 ,7, 2 ,18 ,23, 27 ] for i in range(len(nums)):bigger = -1for j in range(i,len(nums)):if nums[i] < nums[j]:bigger = nums[j]breakres.append(bigger) print(res) # [-1, 22, 23, 18, 18, 18, 23, 27, -1]

如果使用了單調棧+散列表的做法，關于單調棧+散列表的思路，可以查看Leetcode 496官方題解的動畫。

更好的方法就是從左往右掃描，用一個棧記錄右邊的值的一個遞增序列。也就是「典型的散列表+單調棧解決方法。」

思路：遍歷列表，將每一個元素插入到單調棧中，如果單調棧的頭部元素小于插入元素，說明單調棧的頭部元素下一個最大的數，就是當插入元素。于是使用字典進行儲存。最后刪除該單調棧的頭部元素，用插入元素替換。

dict = {} res = [] nums = [44 ,15 ,22, 9 ,7, 2 ,18 ,23, 27 ] for i in range(len(nums)):while res and res[-1] < nums[i]:dict[res.pop()] = nums[i]res.append(nums[i]) while res:dict[res.pop()] = -1 print(dict) # {15: 22, 2: 18, 7: 18, 9: 18, 18: 23, 22: 23, 23: 27, 27: -1, 44: -1} for i in range(len(nums)):nums[i] = dict[nums[i]] print(nums) # [-1, 22, 23, 18, 18, 18, 23, 27, -1]

下面，速度解決Leetcode有關下一個更大的數系列的題目。

Leetcode 496 下一個更大元素 I

輸入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 輸出: [-1,3,-1] 解釋:

對于num1中的數字4，你無法在第二個數組中找到下一個更大的數字，因此輸出 -1。 對于num1中的數字1，第二個數組中數字1右邊的下一個較大數字是 3。 對于num1中的數字2，第二個數組中沒有下一個更大的數字，因此輸出 -1。

對于Leetcode 496，與上面多了一個數列，其實原理都是一樣。下面是解題的代碼。

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:"""方法一：先找到該元素在nums2中的位置，然后再找它之后比它大的時間復雜度：O(n2)"""# res = []# for i in nums1:# flag = 0# bigger = -1# for j in nums2:# if i == j:# flag = 1# if flag == 1 and i < j:# bigger = j# break;# res.append(bigger)# return res"""方法二：為nums2維護一個字典，key為當前元素，value為該元素的下一個比其大的值設置一個遞減棧，當遇到更大的元素時，把棧里比他小的元素都放到字典中查找時只需要在字典中找。時間復雜度O(n+m) 空間復雜度O(m)"""hash_dict = dict()stack = []for i in nums2:while stack and i > stack[-1]:hash_dict[stack.pop()] = istack.append(i)return [hash_dict.get(i,-1) for i in nums1]

Leetcode 503 下一個更大元素 II

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

示例 1: 輸入: [1,2,1] 輸出: [2,-1,2] 解釋: 第一個 1 的下一個更大的數是 2； 數字 2 找不到下一個更大的數； 第二個 1 的下一個最大的數需要循環搜索，結果也是 2。

思路：將數組拷貝一份放在nums數組后面，對新數組進行查找下一個最大元素，上面的解法。

提交代碼的時候，發現由于存在相同的測試案例。所以散列表失效了，可以聲明一個全是-1的res，如果存在更大的數，就進行替換，注意返回的時候需要取長度的一半。對于第一種暴力方法還是通過的。

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:nums = nums + numsstack = []res = [-1] * len(nums)for i in range(len(nums)):while stack and nums[i] > nums[stack[-1]]:small = stack.pop()res[small] = nums[i]stack.append(i)return res[:len(res)//2]

查看官方題解和 labuladong的文章。

官方的題解是通過進行逆序來求解。不懂思路的看官方的動畫，這里不解釋，這種想法很少人知道，具體實現代碼如下。

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:n = len(nums)res = [-1 for _ in range(n)]stack = []for i in range(n*2 -1, -1, -1):while(stack and stack[-1] <= nums[i%n]):stack.pop()res[i%n] = stack[-1] if stack else -1stack.append(nums[i%n])return res

Leetcode 739 每日溫度

請根據每日 氣溫 列表，重新生成一個列表。對應位置的輸出為：要想觀測到更高的氣溫，至少需要等待的天數。如果氣溫在這之后都不會升高，請在該位置用 0 來代替。

例如，給定一個列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應該是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：氣溫 列表長度的范圍是 [1, 30000]。每個氣溫的值的均為華氏度，都是在 [30, 100] 范圍內的整數。

這個問題本質上也是找 Next Greater Number，只不過現在不是問你 Next Greater Number 是多少，而是問你當前距離 Next Greater Number 的距離而已。

使用暴力解的話，代碼大致如下：

def dailyTemperatures(self, T: List[int]) -> List[int]:length = len(T)ans = [0] * lengthfor i in range(length):for j in range(i+1, length):if T[i] < T[j]:ans[i] = j - ibreakreturn ans

由于存在相同的元素散列表+單調棧的做法報廢。因此只有，單調棧+逆序的做法。

class Solution:def dailyTemperatures(self, T: List[int]) -> List[int]:length = len(T)ans = [0] * length# 這里借助列表實現# 列表末尾元素即是棧頂元素stack = []# 從右邊往左邊開始遍歷for i in range(length - 1, -1, -1):# 如果當前元素大于棧頂元素時，進行出棧# 直至當前元素不再大于棧頂元素while stack and T[i] >= T[stack[-1]]:stack.pop()# 這個時候棧頂元素其實就是當前元素右邊第一個比其大的元素，先計算距離，然后入棧if stack and T[i] < T[stack[-1]]:ans[i] = stack[-1] - i# 棧為空的情況下，將當前元素入棧stack.append(i)return ans ? 本文已收錄 GitHub，傳送門~[1] ，里面更有大廠面試完整考點，歡迎 Star。
?

Reference

[1]

傳送門~: https://github.com/MaoliRUNsen/runsenlearnpy100

總結

以上是生活随笔為你收集整理的将一个数组中的值按逆序重新排放。_六十五、下一个更大的数系列，单调栈解决方法...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。