本篇推文共計(jì)2000個(gè)字，閱讀時(shí)間約3分鐘。

題目描述：

給定一個(gè)循環(huán)數(shù)組(最后一個(gè)元素的下一個(gè)元素是數(shù)組的第一個(gè)元素)，輸出每個(gè)元素的下一個(gè)更大元素。

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

示例：

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

注意: 輸入數(shù)組的長度不會超過 10000。

題目有兩個(gè)重點(diǎn)

1.如何求下一個(gè)更大的元素

2.如何實(shí)現(xiàn)循環(huán)數(shù)組

如何求下一個(gè)更大的元素，可以采用構(gòu)建單調(diào)棧的方法來實(shí)現(xiàn)，單調(diào)棧是說棧里面的元素從棧底到棧頂是單調(diào)遞增或者單調(diào)遞減的。

建立[單調(diào)遞減棧]，并對原數(shù)組進(jìn)行遍歷操作：

如果棧為空，

則把當(dāng)前元素放入棧內(nèi)；

如果棧不為空，

則需要判斷當(dāng)前元素和棧頂元素的大小：

如果當(dāng)前元素比棧頂元素大：

說明當(dāng)前元素是前面一些元素的[下一個(gè)更大元素]，則逐個(gè)彈出棧頂元素，直到當(dāng)前元素比棧頂元素小為止。

如果當(dāng)前元素比棧頂元素小：

說明當(dāng)前元素的[下一個(gè)更大元素]與棧頂元素相同，則把當(dāng)前元素入棧。

如何實(shí)現(xiàn)循環(huán)數(shù)組

何為循環(huán)數(shù)組，即為數(shù)組的最后一個(gè)元素的下一個(gè)元素是數(shù)組的第一個(gè)元素

即nums=[1, 2, 1]
循環(huán)數(shù)組為nums[2]=1的下一個(gè)元素是nums[0]=1

對于循環(huán)數(shù)組，我們可以把這個(gè)循環(huán)數(shù)組“拉直”，即復(fù)制該數(shù)組前n-1個(gè)元素拼接在原數(shù)組的后面。

即原數(shù)組nums=[1, 2, 1]
循環(huán)數(shù)組xnums=[1, 2, 1, 1, 2]

同時(shí)對于新構(gòu)建的循環(huán)數(shù)組，

可以使用取模運(yùn)算%可以把下標(biāo)i映射到

原數(shù)組nums長度的0?N內(nèi)

綜上所述，我們的代碼為

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        N=len(nums)
        ret=[-1]*N
        stack=list()

        for i in range(N*2-1):
            while stack and nums[stack[-1]]<nums[i%N]:
                ret[stack.pop()]=nums[i%N]
            stack.append(i%N)
        return ret