1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
int ans = 0;
PriorityQueue<Integer> diffQueue = new PriorityQueue<>();
for (int i = 1; i < heights.length; i++) {
int diff = heights[i] - heights[i - 1];
if (diff <= 0) {
ans += 1;
} else {
diffQueue.offer(diff);
if (diffQueue.size() > ladders) {
int minDiff = diffQueue.poll();
bricks -= minDiff;
if (bricks >= 0) {
ans += 1;
} else {
break;
}
} else {
ans += 1;
}
}
}
return ans;
}
}
|
我们是边走边用梯子, 等到发现梯子没的时候, 我们就需要知道之前走过的buildings中, diff最小的那个是多少, 把那个换成bricks然后我们就又有梯子了. 因此我们用PQ来存遇到的diff中最大的k个, k是梯子的个数, 这k个就用梯子, 其他的就用bricks来走. 等到某个时刻bricks不够用, 此时我们就到了最远的地方, 或者最远的building(最后一个)也被达到了.
时间复杂度: O(nlogk)
空间复杂度: O(k)
