[leetcode] 503. Next Greater Element II @ python

503 Next Greater Element Ii Python

元の質問

循環配列（最後の要素の次の要素は配列の最初の要素）が与えられた場合、すべての要素の次の大きい数値を出力します。数値xの次の大きい数値は、配列内の次のトラバース順序の最初の大きい数値です。つまり、循環検索して、次に大きい数値を見つけることができます。存在しない場合は、この数値に-1を出力します。

例1：
入力：[1,2,1]
出力：[2、-1,2]
説明：最初の1の次に大きい数は2です
番号2は次に大きい番号を見つけることができません
2番目の1の次に大きい数は、循環的に検索する必要があります。これも2です。

解決

スタック。この問題では、より大きな値を見つけるためにループが必要なため、nums prev_lの元の長さを記録し、2つのnumsを接続して新しいnumsを形成し、ansを値-1のリストに初期化します。 numをトラバースすると、それ以上の値はまだ見つかりません。インデックス、値はスタックに入れられます。現在のnがスタックの値よりも大きい場合、スタックは常にポップされ、ansが更新されます。それ以上の値が見つからない場合、結果は初期値-1になり、ansのprev_lの値を返します。

時間：O（2 n）
スペース：O（2 n）

コード

class Solution(object): def nextGreaterElements(self, nums): ''' :type nums: List[int] :rtype: List[int] ''' prev_l = len(nums) nums = nums+nums stack = [] ans = [-1]*len(nums) for i, n in enumerate(nums): while stack and stack[-1][1] < n: prev_i = stack.pop()[0] ans[prev_i] = n stack.append([i, n]) return ans[:prev_l]