1642. Furthest Building You Can Reach - kumaeki/LeetCode GitHub Wiki

1642. 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 (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

解法1

因为梯子是没有高度限制的,所以大的高度差用梯子,梯子用完之后再用砖.
所以, 每次碰到不能到达的地方,先把高度差求出来,放入一个队列.当梯子不够用的时候,取出最小值, 看砖够不够用.

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        
        // 到达当前位置所需砖块的数量
        int sum = 0;     
        // 存储高度差, 每次取出最小值
        PriorityQueue<Integer> que = new PriorityQueue<Integer>();

        // 从第二个位置开始计算
        int index = 1;
        while(index < heights.length){
            int di = heights[index] - heights[index - 1];
            // 如果当前高度不高于前一个高度,可以直接到达, 对下一个高度进行计算
            if(di <= 0){
                index++;
                continue;
            }
            // 如果当前高度高于前一高度
            else{
                // 那么将高度差加入队列
                que.offer(di);
                // 如果梯子的数量足够, 那么可以直接到达, 对下一个高度进行计算
                if(ladders >= que.size()){
                    index++;
                    continue;
                }
                // 如果梯子的数量不够
                else{
                    // 取出que中的最小值,
                    sum += que.poll();
                    // 如果砖块够, 那么可以到达当前高度
                    if(sum <= bricks)
                        index++;
                    // 如果砖块不够, 那么不能到达当前高度
                    else
                        break;
                }
            }
        }
        return index - 1;
    }
}

写的有点乱.稍微整理一下.

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
    
        // 存储高度差, 每次取出最小值
        PriorityQueue<Integer> que = new PriorityQueue<Integer>();

        for(int index = 1;index < heights.length; index++){
            // 当前位置和前一位置的高度差
            int di = heights[index] - heights[index - 1];
            // 如果当前位置高于前一位置
            if(di > 0){
                // 那么将高度差加入队列
                que.offer(di);
                // 如果梯子的数量不够, 那么开始用砖
                if(ladders < que.size()){
                    // 取出que中的最小值
                    bricks -= que.poll();
                    // 如果砖块不够, 那么不能到达当前位置,返回前一位置
                    if(bricks < 0)
                        return index - 1;
                }
            }
        }
        // 到达最后的位置
        return heights.length - 1;
    }
}
⚠️ **GitHub.com Fallback** ⚠️