給你兩個 沒有重復元素 的數組 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

請你找出 nums1 中每個元素在 nums2 中的下一個比其大的值。

nums1 中數字 x 的下一個更大元素是指 x 在 nums2 中對應位置的右邊的第一個比 x 大的元素。如果不存在，對應位置輸出 -1 。

示例：

方法一：雙棧（比暴力法好一點）
解題思路：
定義兩個stack， stack1存num2， stack2作為temp存stack1 pop出來的值默認max=-1 top= stack1.pop()

• if top > num => max = top
• top = num => isfound = True
• top < num => 繼續遍歷

每找到一個元素的下一個更大的值之后，需要將temp棧中的元素放回到stack中，以便用于剩下的其他元素尋找下一個更大的值。

while temp:stack.append(temp.pop())

代碼實戰：

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:stack = []result = []# 將nums2元素全部存入stack棧中for i in nums2:stack.append(i)# 遍歷nums1 開始尋找下一個更大的元素for num in nums1:max = -1temp = []isFound = Falsewhile not isFound:top = stack.pop()if top > num:max = topelif top == num:isFound = Truetemp.append(top)result.append(max)while temp:stack.append(temp.pop())return result

復雜度分析：
時間復雜度O（MN）
空間復雜度O（N）

方法二：單調棧+HashMap
解題思路：

先對 nums2 中的每一個元素，求出它的右邊第一個更大的元素；

將上一步的對應關系放入哈希表（HashMap）中；

再遍歷數組 nums1，根據哈希表找出答案。

代碼實戰：

class Solution:def nextGreaterElement(self, nums1, nums2):d, stack = {}, []for num2 in nums2:while stack and num2 > stack[-1]:d[stack.pop()] = num2stack.append(num2)return [d.get(j, -1) for j in nums1]

復雜度分析：
時間復雜度：O(N + M)，分別遍歷數組 nums1 和數組 nums2 各一次即可，對于 nums2 中的每個元素，進棧一次，出棧一次；
空間復雜度：O(N)。我們在遍歷 nums2 時，需要使用棧，以及哈希映射用來臨時存儲答案。

總結

以上是生活随笔為你收集整理的下一个更大元素 leetcode-496的全部內容，希望文章能夠幫你解決所遇到的問題。

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