JN的電腦日常生活: Leetcode題解 Python：Next Greater Element I & II & III

2020年6月7日星期日

Leetcode題解 Python：Next Greater Element I & II & III

在 contest 前，來抽一題暖手感，剛好就中這一題，有系列就依序解完吧。

(這次的contest有解完)

【Next Greater Element I】

給二個陣列 nums1 和 nums2，nums1 是 nums2 的子集合。

依 nums1 的元素找出(對應nums2位置)下一個比自身大的值。如果沒有則 -1 ，回傳所有的結果 List<int>。

由於 nums1 並非照著原來在 nums2 的相對關係排序，最快的方法是依照 nums1 的元素，在 O(N) Time 解決。

但如果從 nums2 對應的位置開始照規則找，最糟會到 O(N^2) Time。

先找出所有的答案再依 nums1 重組，時間複雜度恰好 O(MN) ，也不用在找答案過程做是否在 nums1 的判斷。

每個元素只要找後方第一個大於它的元素，用一個暫時的「遞增數列」，因為要從後方找，所以從後方開始，就能確保沒有比它大的而馬上填 -1。

(位置不能動，找之於每個元素大或小，或一區段內最大或或最小面積，就可能用上遞增遞減數列)

Python(後往前)

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if not nums1 or not nums2: return []
        memo = dict()        
        result = []
        while nums2:
            num = nums2.pop()          
            while result and result[0] <= num:
                del result[0]
            memo[num] = result[0] if result else -1
            result.insert(0, num)

        return [memo[num] for num in nums1]

Python(Stack)

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if not nums1 or not nums2: return []
        memo = dict()
        result = []
        for i in range(len(nums1)):
            memo[nums1[i]] = i
            result.append(-1)

        stack = []
        for num in nums2:
            while stack and stack[-1] < num:
                if stack[-1] in memo:
                    result[memo[stack[-1]]] = num
                    del memo[stack[-1]] 
                del stack[-1]
            stack.append(num)
        return result

【Next Greater Element II】

一樣的規則，但是變成 circle array，也就是頭接尾。

circle 也可以用系列I的方法，只要把輸入變二倍去解，最後再取原本的長度(題目所求)回傳。

但是擺成二倍等於要跑二偣 N ，也不好。同樣在 O(N) Time ime 也是有高下之分的。

有什麼數字後方一定找不到更大的？最大值，也只有最大值找不到，其餘找到的必 <= 最大值。

把最大值移到最後，就可以用「 Next Greater Element I 」的方法找，再把順序換回所給的順序就能解了。

如：[1,2,1] => [1,1,2] 。只有最大值的解會是 -1 ，因此把最大值放到最後，可確保每個位置答案都正確。

[2,2,-1]，需要換回成 [2,-1,2]，依當初往後挪動多少，就把答案往前挪，舉例是 1 ，故往前挪 1。 [2,2,-1] => [2,-1,2]

Python

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:  
        mi = nums.index(max(nums))
        array = []
        n = len(nums)
        result = [-1 for _ in range(n)]            
        for i in range(n,0,-1):
            ix = (i+mi)%n
            num = nums[ix]   
            while array and array[0] <= num:
                del array[0]
            if array: result[ix] = array[0]
            array.insert(0, num)

        return result

Python(Stack)

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]: 
        if not nums: return nums
        n = len(nums)        
        mi = nums.index(max(nums))       
        result = [-1 for _ in range(n)]          
        stack = []
        for i in range(n):
            ix = (i+mi+1)%n
            num = nums[ix]   
            while stack and nums[stack[-1]] < num:
                result[stack.pop()] = num
            stack.append(ix)           
        return result

【Next Greater Element III】

這題就不在 I、II 的後續，而是一個獨立的題型。

給一個正整數 n ，要找出數字集合相同，下一個更大的數字。更大的可能有很多，要回傳其中最小的。

前面的解法都基於「遞增數列」，這題也是得用這概念去解。

有一個數字集合，其最大值的排法為「非遞增數列」的時候，即 nums[i] >= nums[i+1]。

若反過來從後方看，就是非遞減數列。要使 n 變大一些，從後方開始找是最好的方式。

一旦找到一個數字破壞了非遞減數列，那就代表需要交換此數字、從後方選一個最小的大於此數字交換，然後反轉後方順序。

要交換的數字後方是非遞增數列(排序組合中的最大值)，然而在交換數字後也能保持排序規則。

因此再將順序反轉後，非遞增數列就會變成非遞減數列(排序組合中的最小值)，也就是最小增加。