[Leetcode] 503. Next Greater Element II 503. Next Largeer Element II



503 Next Greater Element Ii 503



1

解決策1:スタック

公式回答: https://leetcode.com/problems/next-greater-element-ii/solution/



実際、要素を探した後、それに最も近い要素はスタックよりも優れています。
スタックを維持し、新しい数に達するたびに、配列を後ろから前にトラバースします。

  1. スタックの最上位がこの数以下の要素をポップします
  2. これで、スタックの一番上の要素がそれに最も近い要素になります。
  3. 新しい番号をそれに押し込みます

ループ配列と非巡回配列の違いは、スタックをリセットせずにループ配列が2回トラバースされることです。



class Solution(object): def nextGreaterElements(self, nums): ''' :type nums: List[int] :rtype: List[int] ''' from collections import deque right = deque() n = len(nums) res = [-1]*n for i in xrange(n-1,-1,-1): while right and nums[right[-1]]<=nums[i]: right.pop() if right: res[i] = nums[right[-1]] right.append(i) for i in xrange(n-1,-1,-1): while right and nums[right[-1]]<=nums[i]: right.pop() if right and res[i]==-1: res[i] = nums[right[-1]] right.append(i) return res

解決策2:第2ラウンドを最適化する

それぞれの数字の後に最も近い値を見つけることを考えていました。
次に、-1とマークされている番号については、その前の彼から最も遠い番号を探します。
前者はスタックで実行できます。
-1とマークされている数値は、その後に大きな数値がないため、配列内で左から右に確実にデクリメントされていることに注意してください。
これらの-1の位置を右から左に(つまり、小さいものから大きいものに)トラバースし、ポインターを維持しますiそして最初に作成する位置を見つけますnums[i]現在の数よりも大きいi
次の数字は現在の数字よりも大きくなければならないので、i前の数字は役に立たないはずなので、増加し続けますiはい、すべての-1がトラバースされるまで、またはiがあります現在のポジション数に達しました

class Solution(object): def nextGreaterElements(self, nums): ''' :type nums: List[int] :rtype: List[int] ''' from collections import deque right = deque() n = len(nums) res = [-1]*n pending = deque() for i in xrange(n-1,-1,-1): while right and nums[right[-1]]<=nums[i]: right.pop() if right: res[i] = nums[right[-1]] else: pending.append(i) right.append(i) i = 0 while pending and i<pending[0]: while i<pending[0] and nums[i]<=nums[pending[0]]: i += 1 if i<pending[0]: res[pending.popleft()] = nums[i] return res