HardRating 2079
975. Odd Even Jump
arraydynamic-programmingstacksortingmonotonic-stackordered-set
解題說明
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 較小的情況。
延伸思考
- 如果奇數跳和偶數跳的規則互換,答案會有什麼變化?
- 如果可以在任意步選擇做奇數跳或偶數跳(而不是交替),問題會怎麼變?
- 如果跳躍不限於向右,也可以向左跳,問題如何處理?