Furthest Building You Can Reach
Medium · heap
A street has a row of buildings, and heights[i] is the height of building i. You start on the roof of building 0 and want to walk along the roofs to the right, always moving from building i to building i + 1.
- If building
i + 1is the same height or lower, you just step across for free. - If it is taller, you must climb the difference
heights[i + 1] - heights[i]. You can do it in one of two ways: spend that many bricks, or use one ladder (a ladder works for any height, and each ladder can be used only once).
You have bricks bricks and ladders ladders. Return the index of the furthest building you can reach.
Examples
Example 1
Input: heights = [1, 3, 2, 6, 4, 5], bricks = 3, ladders = 1
Output: 5
The climbs are 2, 4 and 1. Use the ladder for the climb of 4 and 3 bricks for the other two, which reaches building 5.
Example 2
Input: heights = [5, 9, 3, 8, 20], bricks = 4, ladders = 0
Output: 2
The climb of 4 to building 1 uses all the bricks. Going down to building 2 is free, but the climb of 5 after that cannot be paid.
Example 3
Input: heights = [2, 2, 2], bricks = 0, ladders = 0
Output: 2
No climbing is needed, so the last building is reachable.
Constraints
- 1 <= len(heights) <= 10^5
- 1 <= heights[i] <= 10^6
- 0 <= bricks <= 10^9
- 0 <= ladders <= len(heights)