題目描述: 從陣列中的某個位置開始跳躍。奇數次跳躍跳到右邊 >= 當前值的最小值位置;偶數次跳躍跳到右邊 <= 當前值的最大值位置。如果能跳到陣列末尾,該起始位置就是「好的」。求好的起始位置數量。
解題思路:
時間複雜度: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 較小的情況。