MediumRating 2482

2289. Steps to Make Array Non-decreasing

arraylinked-listdynamic-programmingstackmonotonic-stacksimulation

解題說明

Steps to Make Array Non-decreasing

題目描述：給定一個陣列 nums，每一步操作中，同時移除所有滿足 nums[i-1] > nums[i] 的元素（即左邊鄰居比自己大的元素）。問需要幾步才能使陣列變成非遞減的。

解題思路：使用單調遞減棧。我們從左到右掃描，維護一個棧。對於每個元素，我們需要計算它「存活」多少步。如果一個元素最終會被移除，那麼它被移除的步數取決於它左邊比它大的元素的存活步數。

具體來說，棧中存放 (值, 存活步數) 對。對於當前元素 nums[i]，我們持續彈出棧頂中值 <= nums[i] 的元素，同時追蹤被彈出元素中的最大存活步數 cnt。如果棧不為空（代表有更大的元素在左邊），則 nums[i] 的存活步數為 cnt + 1（它要在那些元素被移除之後才會被移除）。最終答案是所有元素存活步數的最大值。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個元素最多被壓入和彈出棧各一次

空間複雜度：O(n) — 棧最多儲存 n 個元素

虛擬碼

1. Initialize answer = 0, empty stack of (value, steps)
2. For each element x in nums:
   a. Set cnt = 0
   b. While stack is not empty and top value <= x:
      - cnt = max(cnt, top's steps)
      - Pop stack
   c. If stack is empty: steps for x = 0 (x survives forever)
      Else: steps for x = cnt + 1 (x gets removed after cnt steps)
   d. Update answer = max(answer, steps for x)
   e. Push (x, steps for x) onto stack
3. Return answer

其他解法

模擬法：每步掃描陣列移除需要的元素，重複直到沒有元素被移除。時間複雜度 O(n^2)，適合小規模輸入但無法通過本題。
鏈結串列 + BFS/拓撲排序：建立雙向鏈結串列，初始時將所有 nums[i-1] > nums[i] 的 i 加入佇列。每步處理佇列中的所有節點（刪除並更新鄰居），如果新的鄰居關係產生違反則加入下一輪佇列。時間複雜度 O(n)，但實作較複雜。

延伸思考

如果操作改為移除「右邊鄰居比自己大的元素」，演算法需要如何修改？
如果不是同時移除，而是每步只移除第一個違反的元素，答案會如何改變？
如果要求返回每步被移除的元素列表（而非步數），如何高效實現？

Steps to Make Array Non-decreasing — CaffeCode