Python程式查詢右側的迴圈最大元素

假設我們有一個名為 nums 的數字列表。我們必須找到一個相同長度的新列表，其中索引 i 處的值分配給其右側的下一個大於 nums[i] 的元素，並在需要時迴圈回到列表的前面。如果沒有大於的數字，則應將其設定為 -1。

因此，如果輸入類似於 [4, 5, 1, 3]，則輸出將為 [5, -1, 3, 4]

為了解決這個問題，我們將遵循以下步驟：

• n := a 的大小

• stack := 一個棧，最初插入 0，res := 一個大小為 n 的列表，並填充 -1

• 對於範圍 0 到 1 中的每個值，執行以下操作

  • 對於從 0 到 n-1 的範圍內的每個 i，執行以下操作

  • 當 stack 不為空且 a[棧頂] < a[i] 時，執行以下操作

    • res[棧頂] := a[i]

    • 刪除棧中的最後一個元素

  • 在棧的末尾插入 i

• 返回 res

讓我們看看以下實現以獲得更好的理解：

示例

 線上演示

class Solution:
   def solve(self, a):
      n = len(a)
      stack, res = [0], [-1] * n
      for _ in range(2):
         for i in range(n):
            while stack and a[stack[-1]] < a[i]:
               res[stack[-1]] = a[i]
               stack.pop()
            stack.append(i)
   return res
ob = Solution()
nums = [4, 5, 1, 3]
print(ob.solve(nums))

輸入

[4, 5, 1, 3]

輸出

[5, -1, 3, 4]

Arnab Chakraborty

更新於: 2020年10月5日

119 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習