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
(h[i+1] - h[i])
bricks.
Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.
Example 1:
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1 Output: 4 Explanation: Starting at building 0, you can follow these steps: - Go to building 1 without using ladders nor bricks since 4 >= 2. - Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7. - Go to building 3 without using ladders nor bricks since 7 >= 6. - Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9. It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
Example 2:
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 Output: 7
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0 Output: 3
Constraints:
1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length
Solution 0: DFS
Time complexity: O(2^n)
Space complexity: O(n)
AC but should be TLE
Solution 1: Binary Search + Greedy
Guess we can reach to m, sort the height differences from 0~m. Use ladders for larger values and use bricks for smallest values left.
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 300 ms class Solution { public: int furthestBuilding(vector<int>& heights, int bricks, int ladders) { const int n = heights.size(); if (ladders >= n - 1) return n - 1; vector<int> diffs(n); for (int i = 1; i < n; ++i) diffs[i - 1] = max(0, heights[i] - heights[i - 1]); int l = ladders; int r = n; while (l < r) { int m = l + (r - l) / 2; vector<int> d(begin(diffs), begin(diffs) + m); nth_element(begin(d), end(d) - ladders, end(d)); if (accumulate(begin(d), end(d) - ladders, 0) > bricks) r = m; else l = m + 1; } return l - 1; } }; |
Solution 2: Min heap
Use a min heap to store all the height differences ( > 0) so far, if heap size is greater than ladders, which means we have to use bricks, extract the smallest value and subtract the bricks.
Time complexity: O(nlogk)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 216 ms class Solution { public: int furthestBuilding(vector<int>& heights, int bricks, int ladders) { const int n = heights.size(); priority_queue<int, vector<int>, greater<int>> q; for (int i = 1; i < n; ++i) { const int d = heights[i] - heights[i - 1]; if (d <= 0) continue; q.push(d); if (q.size() <= ladders) continue; bricks -= q.top(); q.pop(); if (bricks < 0) return i - 1; } return n - 1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment