702. Cheapest Climb
A hiking trail runs over n marker posts numbered from 0. Leaving post i costs a toll of cost[i], and every move takes you either one post or two posts further along the trail. You may begin your hike standing on post 0 or on post 1. The summit is the spot just beyond the last post, at index n.
Return the smallest total toll you must pay to reach the summit. Paying is only needed for the posts you actually leave, and a jump from one of the last two posts reaches the summit directly.
Aim for time O(n) and extra space O(1).
Example 1
- Input:
- cost = [12,4,30,6,20,3]
- Output:
- 13
- Explanation:
Start on post 1 (toll 4), jump to post 3 (toll 6), jump to post 5 (toll 3) and then to the summit, for a total of 13.
Example 2
- Input:
- cost = [8,15]
- Output:
- 8
- Explanation:
Start on post 0, pay 8 and jump two posts straight to the summit; starting on post 1 would cost 15.
Constraints
2 ≤ n = cost.length ≤ 105
0 ≤ cost[i] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)