HardRating 2079

975. Odd Even Jump

arraydynamic-programmingstacksortingmonotonic-stackordered-set

在 LeetCode 上作答 ↗

解題說明

Odd Even Jump

題目描述：從陣列中的某個位置開始跳躍。奇數次跳躍跳到右邊 >= 當前值的最小值位置；偶數次跳躍跳到右邊 <= 當前值的最大值位置。如果能跳到陣列末尾，該起始位置就是「好的」。求好的起始位置數量。

解題思路：

動態規劃 + 有序映射：從右往左處理，用 ordered map 維護值到索引的映射。
對每個位置 i，判斷：(a) 奇數跳能否最終到達終點 (b) 偶數跳能否最終到達終點。
奇數跳目標：在 map 中找 >= nums[i] 的最小值（lower_bound）。
偶數跳目標：在 map 中找 <= nums[i] 的最大值（upper_bound 後退一步）。
dp[i][odd] = true 表示從位置 i 出發，下一步是奇數跳時能到達終點。
最後一個位置永遠是好的。從位置 i 開始的第一步是奇數跳。

C++ 解法

複雜度分析

時間複雜度：O(n log n) — 每個元素在有序映射中進行 O(log n) 的查詢和插入

空間複雜度：O(n) — 有序映射和 DP 陣列

虛擬碼

1. Initialize odd[] and even[] arrays, both false
2. Set odd[n-1] = even[n-1] = true (last position is always good)
3. Create ordered map: value -> index
4. Insert arr[n-1] into map
5. For i = n-2 down to 0:
   a. Odd jump: find lower_bound(arr[i]) in map -> target index j
      - If found: odd[i] = even[j]
   b. Even jump: find upper_bound(arr[i]) then go back one step -> target index j
      - If found: even[i] = odd[j]
   c. If odd[i] is true, increment answer
   d. Insert arr[i] -> i into map
6. Return answer

其他解法

單調棧方法：先對數組做兩次排序（一次按值升序用於奇數跳，一次按值降序用於偶數跳），用單調棧找出每個位置的跳躍目標。然後從後往前 DP。時間複雜度同為 O(n log n)，但避免了使用有序映射。
暴力搜尋：對每個起始位置模擬跳躍過程。每次跳躍都遍歷右邊所有元素找目標。時間複雜度 O(n^2)，適合 n 較小的情況。

延伸思考

如果奇數跳和偶數跳的規則互換，答案會有什麼變化？
如果可以在任意步選擇做奇數跳或偶數跳（而不是交替），問題會怎麼變？
如果跳躍不限於向右，也可以向左跳，問題如何處理？

Odd Even Jump — CaffeCode