Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.
Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.
Note: The length of given array won't exceed 10000.
解題思路：
題意為：給一個(gè)循環(huán)列表（最后一個(gè)元素與第一個(gè)元素相同）拦宣，求出列表中每個(gè)元素的下一個(gè)較大的元素是什么（最大值沒(méi)有下一個(gè)較大的元素，對(duì)應(yīng)位置為-1）祥国。
以 nums = [100,9,1,11,1,120,111,123,1,-1,-100,103,98,100] 為例阁谆，我們可以觀察到幾個(gè)性質(zhì)：
- 在最大值（123）左側(cè)碳抄，如果前面的數(shù)比后面的數(shù)小，則把后面的數(shù)當(dāng)做較大值（如 9 < 11）场绿；
- 在最大值（123）右側(cè)剖效，如果一直到列表結(jié)束都找不到較大的數(shù)（如103），則需要重新再遍歷一次列表焰盗，找到下一個(gè)較大的數(shù)（120）璧尸。
- 思路一：
- 設(shè)置兩個(gè)指針 i 和 j，i 始終指向當(dāng)前元素熬拒。然后爷光，將 nums 擴(kuò)寬 2 倍，j 每次指向下一個(gè)較大的元素澎粟。當(dāng) i 的指針達(dá)到原 nums 的長(zhǎng)度蛀序，則退出循環(huán)。注意活烙，當(dāng) i 指向 103徐裸，j 向后找到 120，然后啸盏，j 還要回退到 i 的下一個(gè)位置重贺，不然，98就找不到下一個(gè)較大的數(shù) 100。這種情況下檬姥，最壞時(shí)間復(fù)雜度為 O(n^2)曾我，Python3 版本會(huì)超時(shí)（C++ 和 Java不會(huì)）。
- 思路二：
- 使用一個(gè)棧健民，遍歷列表抒巢，棧中存放還未確定下一個(gè)較大元素的下標(biāo)，如果遇到一個(gè)較大的數(shù)秉犹，則進(jìn)入一個(gè)新的循環(huán)蛉谜，把未確定的元素出棧，直到棧中留下的元素比當(dāng)前的元素大崇堵。（比如型诚，[100,9,1] 都先放入棧中，因?yàn)樗鼈兌歼€未找到較大的元素鸳劳，下一次狰贯，遇到 11，則 1 比 11 小赏廓，1 出棧涵紊；此時(shí)繼續(xù)循環(huán)判斷棧中的 9, 9 也比 11 小，9 出棧幔摸；100 比 11 大摸柄，則棧中元素不能在確定下一個(gè)較大的元素了，則 11 入棧既忆，繼續(xù)遍歷列表）驱负。
- 當(dāng)一次遍歷結(jié)束后，只有 [123,103,100] 還在棧中患雇。這時(shí)跃脊，只需要重新再次遍歷一遍列表，100 比 120 小庆亡，出棧匾乓；103 比 120 小捞稿，出棧又谋；直到再次遇到最大數(shù)123，則循環(huán)結(jié)束娱局。
- 因?yàn)椴簧婕爸羔樆赝苏煤ィ瑒t時(shí)間復(fù)雜度 O(n)，但空間復(fù)雜度 O(n)
Python 實(shí)現(xiàn)：
class Solution:
# 超時(shí)版本：最壞時(shí)間復(fù)雜度為 O(n^2)
def nextGreaterElements(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
lens = len(nums)
if lens == 0:
return []
maxnum = max(nums) # nums 中的最大值
nums = nums + nums # 將 nums 擴(kuò)展成 2 倍長(zhǎng)
ret = [] # 返回值
i = j = 0 # i 指向當(dāng)前數(shù)衰齐，j 指向下一個(gè)較大數(shù)
while i < lens:
if nums[i] == maxnum: # 最大值位置直接為 -1
ret.append(-1)
i += 1; j += 1
elif nums[i] < nums[j]:
ret.append(nums[j])
i += 1; j = i + 1 # j 指針回退
else:
j += 1
return ret
# AC版本：最壞時(shí)間復(fù)雜度為 O(n)任斋，但空間復(fù)雜度也為 O(n)
def nextGreaterElements2(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
lens = len(nums)
if lens == 0:
return []
maxnum = max(nums) # nums 中的最大值
ret = [-1] * lens # 返回值
stack = [] # 存儲(chǔ)還未確定的下一個(gè)較大數(shù)的元素
for i in range(lens):
while stack and nums[stack[-1]] < nums[i]:
ret[stack.pop()] = nums[i]
stack.append(i)
# print(stack)
for i in range(lens):
while stack and nums[stack[-1]] < nums[i]:
ret[stack.pop()] = nums[i]
if maxnum == nums[i]:
break
return ret
a = [3,1,4,2,5,3]
a = [3,5,4,2,5,1,3]
a = [3,1,5,4,6,5,2,6,5,4,3]
a = [6,5,3,1,4,5,6,7,6,5,4,3,2,6]
a = [100,9,1,11,1,120,111,123,1,-1,-100,103,98,100]
print(Solution().nextGreaterElements2(a))
# [120, 11, 11, 120, 120, 123, 123, -1, 103, 103, 103, 120, 100, 120]
