Furthest Building You Can Reach
You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.
You start your journey from building 0 and move to the next building by possibly using bricks or ladders.
While moving from building i to building i + 1 (0-indexed):
- If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
- If the current building's height is less than the next building's height, you can either use one ladder or
heights[i + 1] - heights[i]bricks.
Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.
Example 1
#
#
# #
# #
# #
# # #
# # #
# # # #
# # # # #
# # # # #
# # # # # #
# # # # # #
# # # # # # #
# # # # # # #
4 2 7 6 9 14 12Input
heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1Output
4You can reach building 4 by using 5 bricks for the climb from building 1 to 2 and the only ladder for the climb from building 3 to 4, but you cannot go further.
Example 2
#
# #
# # #
# # #
# # #
# # #
# # #
# # #
# # # #
# # # #
# # # #
# # # #
# # # #
# # # # #
# # # # #
# # # # #
# # # # # #
# # # # # # # #
# # # # # # # # #
# # # # # # # # #
4 12 2 7 3 18 20 3 19Input
heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2Output
7Using the bricks and ladders optimally allows you to reach building 7, but not the final climb to building 8.
Constraints
- 1 <= heights.length <= 10^5
- 1 <= heights[i] <= 10^6
- 0 <= bricks <= 10^9
- 0 <= ladders <= heights.length