題目描述

給定一個長度為 n 的下標從?0?開始的整數數組?nums。初始位置為下標?0。當?i < j?時，你可以從下標?i?跳轉到下標?j:

• 對于在?i < k < j?范圍內的所有下標?k?有?nums[i] <= nums[j]?和?nums[k] < nums[i]?, 或者
• 對于在?i < k < j?范圍內的所有下標?k?有?nums[i] > nums[j]?和?nums[k] >= nums[i]?。

你還得到了一個長度為?n?的整數數組?costs，其中?costs[i]?表示跳轉到下標?i?的代價。

返回跳轉到下標?n - 1?的最小代價。

示例 1:

輸入: nums = [3,2,4,4,1], costs = [3,7,6,4,2]
輸出: 8
解釋: 從下標 0 開始。
- 以 costs[2]= 6 的代價跳轉到下標 2。
- 以 costs[4]= 2 的代價跳轉到下標 4。
總代價是 8。可以證明，8 是所需的最小代價。
另外兩個可能的路徑是:下標 0 -> 1 -> 4 和下標 0 -> 2 -> 3 -> 4。
它們的總代價分別為9和12。

示例?2:

輸入: nums = [0,1,2], costs = [1,1,1]
輸出: 2
解釋: 從下標 0 開始。
- 以 costs[1] = 1 的代價跳轉到下標 1。
- 以 costs[2] = 1 的代價跳轉到下標 2。
總代價是 2。注意您不能直接從下標 0 跳轉到下標 2，因為 nums[0] <= nums[1]。

解釋:

• n == nums.length == costs.length
• 1 <= n <= 10^5
• 0 <= nums[i], costs[i] <= 10^5

---

問題分析

這道題是跳躍游戲系列中的一道具有挑戰性的題目。關鍵在于理解跳躍條件：

跳躍條件解析：

• 條件一：?nums[i] <=?nums[j]?且中間所有?nums[k]?< nums[i]

  • 含義：從位置i跳到右側第一個?≥ nums[i]?的位置

  • 對應：單調遞減棧（維護一個從棧底到棧頂遞減的序列）

• 條件二：?nums[i] > nums[j]?且中間所有?nums[k] >=?nums[i]

  • 含義：從位置i跳到右側第一個?< nums[i]?的位置

  • 對應：單調遞增棧（維護一個從棧底到棧頂遞增的序列）

這兩個條件實際上是互補的，可以用單調棧來高效處理。

---

解題思路

單調棧?+ 動態規劃

核心思想：

1. 使用兩個單調棧分別處理兩種跳躍條件
2. 用動態規劃記錄到達每個位置的最小代價
3. 從左到右遍歷，動態更新可達位置的最小代價

算法步驟：

• 初始化?dp[i]?表示到達位置 i?的最小代價，dp[0] =?0
• 維護兩個單調棧：
  • stack1：處理條件一（單調遞減棧）
  • stack2：處理條件二（單調遞增棧）
• 對每個位置 j，檢查能從哪些位置跳到?j，并更新最小代價

---

算法過程

輸入：?nums = [3,2,4,4,1],?costs = [3,7,6,4,2]

初始狀態

位置:    0  1  2  3  4
nums:   [3, 2, 4, 4, 1]
costs:  [3, 7, 6, 4, 2]
dp:     [0, ∞, ∞, ∞, ∞]stack1: []  (單調遞減棧 - 處理條件一)
stack2: []  (單調遞增棧 - 處理條件二)

步驟1：處理位置0 (nums[0] = 3)

當前位置 j = 0, nums[0] = 3stack1操作：
- 棧為空，直接入棧
- stack1: [0]stack2操作：
- 棧為空，直接入棧  
- stack2: [0]dp狀態：[0, ∞, ∞, ∞, ∞]

步驟2：處理位置1 (nums[1]?= 2)

當前位置 j = 1, nums[1] = 2stack1操作（條件一）：
- nums[stack1.top()] = nums[0] = 3 > nums[1] = 2
- 不滿足 nums[i] <= nums[j]，不彈出
- stack1: [0, 1]stack2操作（條件二）：
- nums[stack2.top()] = nums[0] = 3 > nums[1] = 2 ?
- 彈出位置0，更新 dp[1] = min(∞, dp[0] + costs[1]) = min(∞, 0 + 7) = 7
- 將位置1入棧
- stack2: [1]dp狀態：[0, 7, ∞, ∞, ∞]跳躍路徑：0 → 1 (代價7)

步驟3：處理位置2 (nums[2]?= 4)

當前位置 j = 2, nums[2] = 4stack1操作（條件一）：
- nums[1] = 2 <= nums[2] = 4 ?，彈出位置1dp[2] = min(∞, dp[1] + costs[2]) = min(∞, 7 + 6) = 13
- nums[0] = 3 <= nums[2] = 4 ?，彈出位置0  dp[2] = min(13, dp[0] + costs[2]) = min(13, 0 + 6) = 6
- 將位置2入棧
- stack1: [2]stack2操作（條件二）：
- nums[1] = 2 < nums[2] = 4，不滿足條件二，不彈出
- 將位置2入棧
- stack2: [1, 2]dp狀態：[0, 7, 6, ∞, ∞]跳躍路徑：0 → 2 (代價6) 或 0 → 1 → 2 (代價13)
最優：0 → 2 (代價6)

步驟4：處理位置3 (nums[3] =?4)

當前位置 j = 3, nums[3] = 4stack1操作（條件一）：
- nums[2] = 4 <= nums[3] = 4 ?，彈出位置2dp[3] = min(∞, dp[2] + costs[3]) = min(∞, 6 + 4) = 10
- 將位置3入棧
- stack1: [3]stack2操作（條件二）：
- nums[2] = 4 不大于 nums[3] = 4，不彈出
- 將位置3入棧
- stack2: [1, 2, 3]dp狀態：[0, 7, 6, 10, ∞]跳躍路徑：0 → 2 → 3 (代價10)

步驟5：處理位置4?(nums[4] = 1)

當前位置 j = 4, nums[4] = 1stack1操作（條件一）：
- nums[3] = 4 > nums[4] = 1，不滿足條件一，不彈出
- 將位置4入棧
- stack1: [3, 4]stack2操作（條件二）：
- nums[3] = 4 > nums[4] = 1 ?，彈出位置3dp[4] = min(∞, dp[3] + costs[4]) = min(∞, 10 + 2) = 12
- nums[2] = 4 > nums[4] = 1 ?，彈出位置2dp[4] = min(12, dp[2] + costs[4]) = min(12, 6 + 2) = 8
- nums[1] = 2 > nums[4] = 1 ?，彈出位置1dp[4] = min(8, dp[1] + costs[4]) = min(8, 7 + 2) = 9
- 最終 dp[4] = 8
- stack2: [4]dp狀態：[0, 7, 6, 10, 8]跳躍路徑：0 → 2 → 4 (代價8)

最優路徑

最終答案：dp[4] = 8最優路徑：0 → 2 → 4
詳細分析：
- 從位置0跳到位置2：滿足條件一 (nums[0]=3 <= nums[2]=4，中間nums[1]=2 < nums[0]=3)
- 從位置2跳到位置4：滿足條件二 (nums[2]=4 > nums[4]=1，中間nums[3]=4 >= nums[2]=4)
- 總代價：costs[2] + costs[4] = 6 + 2 = 8

---

詳細代碼實現

Java?實現

class Solution {public long minCost(int[] nums, int[] costs) {int n = nums.length;long[] dp = new long[n];// 初始化dp數組Arrays.fill(dp, Long.MAX_VALUE);dp[0] = 0;  // 起始位置代價為0// 兩個單調棧Deque<Integer> stack1 = new ArrayDeque<>();  // 處理條件一Deque<Integer> stack2 = new ArrayDeque<>();  // 處理條件二for (int j = 0; j < n; j++) {// 處理條件一：nums[i] <= nums[j] 且中間元素都小于 nums[i]// 單調遞減棧，當遇到更大的元素時彈出while (!stack1.isEmpty() && nums[stack1.peek()] <= nums[j]) {int i = stack1.pop();dp[j] = Math.min(dp[j], dp[i] + costs[j]);}stack1.push(j);// 處理條件二：nums[i] > nums[j] 且中間元素都大于等于 nums[i]// 單調遞增棧，當遇到更小的元素時彈出while (!stack2.isEmpty() && nums[stack2.peek()] > nums[j]) {int i = stack2.pop();dp[j] = Math.min(dp[j], dp[i] + costs[j]);}stack2.push(j);}return dp[n - 1];}
}

C# 實現

public class Solution {public long MinCost(int[] nums, int[] costs) {int n = nums.Length;long[] dp = new long[n];// 初始化dp數組for (int i = 0; i < n; i++) {dp[i] = long.MaxValue;}dp[0] = 0;  // 起始位置代價為0// 兩個單調棧Stack<int> stack1 = new Stack<int>();  // 處理條件一Stack<int> stack2 = new Stack<int>();  // 處理條件二for (int j = 0; j < n; j++) {// 處理條件一：nums[i] <= nums[j] 且中間元素都小于 nums[i]while (stack1.Count > 0 && nums[stack1.Peek()] <= nums[j]) {int i = stack1.Pop();dp[j] = Math.Min(dp[j], dp[i] + costs[j]);}stack1.Push(j);// 處理條件二：nums[i] > nums[j] 且中間元素都大于等于 nums[i]while (stack2.Count > 0 && nums[stack2.Peek()] > nums[j]) {int i = stack2.Pop();dp[j] = Math.Min(dp[j], dp[i] + costs[j]);}stack2.Push(j);}return dp[n - 1];}
}

---

時間復雜度和空間復雜度

• 時間復雜度：O(n)?- 每個元素最多入棧和出棧一次
• 空間復雜度：O(n)?- dp數組和兩個棧的空間