leetcode如何解決下一個更大元素問題

小編給大家分享一下leetcode如何解決下一個更大元素問題，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

一、題目內容

給定一個循環數組（最后一個元素的下一個元素是數組的第一個元素），輸出每個元素的下一個更大元素。數字 x 的下一個更大的元素是按數組遍歷順序，這個數字之后的第一個比它更大的數，這意味著你應該循環地搜索它的下一個更大的數。如果不存在，則輸出 -1。

示例 1:

輸入: [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數是 2；
數字 2 找不到下一個更大的數； 
第二個 1 的下一個最大的數需要循環搜索，結果也是 2。

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

二、解題思路

將列表nums二次拼接，然后res存儲每個數字下一個更大的元素，s存儲每個元素的下標；

當前元素(s中棧頂對應的nums元素的下一個)大于s中棧頂對應的nums元素，res對應的s棧頂下標的下一個更大的元素為當前元素，s彈出棧頂下標；

s只存儲nums長度的下標，而不是二次拼接之后的數組下標；

三、代碼

class Solution:
    def nextGreaterElements(self, nums: list) -> list:
        res = [-1 for _ in range(len(nums))]
        s = []

        two_nums = nums + nums
        for i in range(len(two_nums)):
            while s and nums[s[-1]] < two_nums[i]:
                res[s[-1]] = two_nums[i]  # 當前元素(s中棧頂對應的nums元素的下一個)大于s中棧頂對應的nums元素
                s.pop()  # pop的是下標
            # i大于nums的長度了就不往s里添加下標了
            if i < len(nums):
                s.append(i)
        return res


if __name__ == '__main__':
    s = Solution()
    nums = [1, 2, 1]
    ans = s.nextGreaterElements(nums)
    print(ans)

以上是“leetcode如何解決下一個更大元素問題”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！