By Long Luo

This article is the solution Priority Queue + Greedy: Consider Ladder as a One-time Unlimited Bricks of Problem 1642. Furthest Building You Can Reach.

Intuition

While we are moving, we will need to use bricks or ladders several times. Suppose we have to move to the next building, which means we must use one ladder or \(\Delta h\) bricks, so there is a question, whether to use ladders or bricks?

If the gap of buildings is large, we may use the ladder, otherwise we use the bricks.

We can consider ladder as a one-time unlimited number of bricks, That is, if we have l ladders, we will use the ladder on the \(l\) times where \(\Delta h\) is the largest, and use the bricks in the rest.

Therefore, we got the answer. We maintain no more than \(l\) largest \(\Delta h\) using priority queues, and these are where the ladders are used. For the remaining \(\Delta h\), we need to use bricks, so we need to accumulate them, if the \(sum\) exceeds the number of bricks \(b\), then we have move to the furthest building.

The code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public int furthestBuilding(int[] heights, int bricks, int ladders) {
    int len = heights.length;

    PriorityQueue<Integer> gaps = new PriorityQueue<>((o1, o2) -> o1 - o2);

    int sum = 0;
    for (int i = 0; i < len - 1; i++) {
        int deltaHeight = heights[i + 1] - heights[i];
        if (deltaHeight > 0) {
            gaps.offer(deltaHeight);
            if (gaps.size() > ladders) {
                sum += gaps.poll();
            }

            if (sum > bricks) {
                return i;
            }
        }
    }

    return len - 1;
}

Analysis

Time Complexity: \(O(n \log l)\) Space Complexity: \(O(l)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗