503. 下一個更大元素 II

• 題目
• • 我的解答
  • • 分析
    • 解答
  • 官方解法

題目

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

示例 1:

輸入: [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數(shù)是 2；
數(shù)字 2 找不到下一個更大的數(shù)；
第二個 1 的下一個最大的數(shù)需要循環(huán)搜索，結(jié)果也是 2。
注意: 輸入數(shù)組的長度不會超過 10000。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/next-greater-element-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

我的解答

分析

參考496. 下一個更大元素 I，一個很直接的方式是套用之前的解法，但是這道題有點不同，I的數(shù)組無重復(fù)元素。但是II中的元素可以到循環(huán)到數(shù)組前面去查找下一個元素。所以不能用元素之作為鍵值構(gòu)建字典了
循環(huán)數(shù)組的一個技巧就是*2

解答

因為不能用元素之作為鍵值構(gòu)建字典，但是每一個元素的位置是唯一的，可以用元素的位置作為鍵值。

• 構(gòu)建兩個棧：保存位置的stack_index和保存元素值的stack_element，以及保存字典dic（key是位置，value是下一個更大的值。沒有下一個更大值的不會保存在字典中–比如最大值）
• 接下來的思路同I：
  • 遍歷2*nums –item
    • 如果棧為空，索引和元素值分別入棧。
    • 如果棧為非空，且item>stack_element棧頂，加入字典。dic[stack_index.pop()]=item,stack_element.pop()
    • 如果棧為非空，且item<stack_element棧頂,分別壓棧stack_index和stack_element。
• 遍歷序列[0,1,2..,n-1],如果字典中存在相應(yīng)的索引，則取值為dic[index],否則為-1

class Solution:def nextGreaterElements(self, nums):stack_index = []stack_element = []dic = {}# 記錄元素位置相應(yīng)的下一個更大值for index,item in enumerate(2*nums):while stack_element and stack_element[-1]<item:dic[stack_index.pop()]=itemstack_element.pop()else:stack_element.append(item)stack_index.append(index)result = []for i in range(len(nums)):if i in dic:result.append(dic[i])else:result.append(-1)return result

精簡一點，可以省去一個數(shù)組stack_element

• stack_element相當于是取nums中的值。由于stack_element與stack_index是同步變化的。通過nums和stack_index即可實現(xiàn)。
• 遍歷的索引的位置在nums中的實際位置是index%l

class Solution:def nextGreaterElements(self, nums):l = len(nums)stack_index = []dic = {}# 記錄元素位置相應(yīng)的下一個更大值res = []# 記錄元素位置相應(yīng)的下一個更大值for index,item in enumerate(2*nums):while stack_index and nums[stack_index[-1]%l]<item:dic[stack_index.pop()]=itemelse:stack_index.append(index%l)result = []for i in range(len(nums)):if i in dic:result.append(dic[i])else:result.append(-1)return result

官方解法

• 新建stack保存索引。新建保存結(jié)果數(shù)組res與nums的長度相同，保存下一個更大值。
• stack是單調(diào)遞減棧（不是索引是單調(diào)遞減的，而是索引相應(yīng)的元素值是單調(diào)遞減。其實是為了確保棧中是下一個稍大的值）。
  從后向前遍歷兩次列表，遍歷到第i個元素，
• 如果stack為空，索引入棧，同時res[i%l]=-1。
• 如果stack為非空：
  • 當前棧頂元素nums[stack[-1]]<遍歷到的nums[i%l],那么彈出棧頂元素。此時前面元素的更大值是nums[i%l]。同時res[i%l]=-1，將i%l壓入棧。
  • 當前棧頂元素nums[stack[-1]]>遍歷到的nums[i%l],res[i%l]=nums[stack[-1]],然后將i%l壓入棧。
• 返回res

這種方法要確保局部有序

class Solution:def nextGreaterElements(self, nums):l = len(nums)stack = []res = [-1]*lfor i in range(2*l-1,-1,-1):while stack and nums[stack[-1]]<=nums[i%l]:stack.pop()res[i%l] = -1 if not stack else nums[stack[-1]]stack.append(i%l)return res

總結(jié)

以上是生活随笔為你收集整理的503. 下一个更大元素 II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。