在 contest 前，來抽一題暖手感，剛好就中這一題，有系列就依序解完吧。
(這次的contest有解完)
【Next Greater Element I】
給二個陣列 nums1 和 nums2，nums1 是 nums2 的子集合。
依 nums1 的元素找出(對應nums2位置)下一個比自身大的值。如果沒有則 -1 ，回傳所有的結果 List。
由於 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 變大一些，從後方開始找是最好的方式。
一旦找到一個數字破壞了非遞減數列，那就代表需要交換此數字、從後方選一個最小的大於此數字交換，然後反轉後方順序。
要交換的數字後方是非遞增數列(排序組合中的最大值)，然而在交換數字後也能保持排序規則。
因此再將順序反轉後，非遞增數列就會變成非遞減數列(排序組合中的最小值)，也就是最小增加。
Python
class Solution:
def nextGreaterElement(self, n: int) -> int:
stack = [n % 10]
n //= 10
while n and n % 10 >= stack[-1]:
stack.append(n % 10)
n //= 10
if not n: return -1
num_change = n % 10
stack.sort()
l, r = 0, len(stack)
while l < r:
m = (r-l)//2 + l
if stack[m] <= num_change:
l = m+1
else:
r = m
if r < len(stack):
n, stack[r] = (n-n%10+stack[r]), num_change
for num in stack:
n = n*10 + num
return n if n <= 2**31-1 else -1