leetcode如何解決下一個(gè)更大元素問題

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

一、題目內(nèi)容

給定一個(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:

輸入: [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。

二、解題思路

將列表nums二次拼接，然后res存儲每個(gè)數(shù)字下一個(gè)更大的元素，s存儲每個(gè)元素的下標(biāo)；

當(dāng)前元素(s中棧頂對應(yīng)的nums元素的下一個(gè))大于s中棧頂對應(yīng)的nums元素，res對應(yīng)的s棧頂下標(biāo)的下一個(gè)更大的元素為當(dāng)前元素，s彈出棧頂下標(biāo)；

s只存儲nums長度的下標(biāo)，而不是二次拼接之后的數(shù)組下標(biāo)；

三、代碼

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]  # 當(dāng)前元素(s中棧頂對應(yīng)的nums元素的下一個(gè))大于s中棧頂對應(yīng)的nums元素
                s.pop()  # pop的是下標(biāo)
            # i大于nums的長度了就不往s里添加下標(biāo)了
            if i < len(nums):
                s.append(i)
        return res


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

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