可以到达的最远建筑

1642. 可以到达的最远建筑

难度中等53收藏分享切换为英文接收动态反馈

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：

• 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
• 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块

如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。

示例 1：

输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
输出：4
解释：从建筑物 0 出发，你可以按此方案完成旅程：
- 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
- 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
无法越过建筑物 4 ，因为没有更多砖块或梯子。

示例 2：

输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输出：7

示例 3：

输入：heights = [14,3,19,3], bricks = 17, ladders = 0
输出：3

提示：

• 1 <= heights.length <= 105
• 1 <= heights[i] <= 106
• 0 <= bricks <= 109
• 0 <= ladders <= heights.length

记忆化搜索(超时+超内存)

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        dp = new int[bricks+1][ladders+1];
        return backtrack(heights,1,bricks,ladders);
    }

    int max = 0;
    int [][]dp;
    public int backtrack(int[] heights,int index,int bricks,int ladders){
        if(index == heights.length || 
            (bricks < heights[index] - heights[index-1] && ladders==0)){
            return index-1;
        }
        if(dp[bricks][ladders]!=0)return dp[bricks][ladders];

        int tempMax = 0;
        // 如果当前的高度小于前一个高度,那么到当前的位置不需要梯子或砖块
        if(heights[index] < heights[index-1]){
            dp[bricks][ladders] = backtrack(heights,index+1,bricks,ladders);
            return dp[bricks][ladders];
        }else{
            int need = heights[index] - heights[index-1];
            if(need <= bricks){
                int v1 = 0,v2 = 0;
                // 可以使用砖块
                v1 = backtrack(heights,index+1,bricks-need,ladders);
                // 可以使用梯子
                if(ladders > 0)v2 = backtrack(heights,index+1,bricks,ladders-1);
                dp[bricks][ladders] = Math.max(v1,v2);
                return dp[bricks][ladders];
            }else{
                // 只能使用梯子
                if(ladders > 0){
                    dp[bricks][ladders] = backtrack(heights,index+1,bricks,ladders-1);
                    return dp[bricks][ladders];
                } 
            }
        }
        return 0;
    }
}

贪心（重要题型）

思路：优先使用梯子，如果梯子不够了，选择最小的那个gap，然后将这个gap换成砖块，一直替换，直至当前剩余的砖块不够往下一个index继续走并且梯子的数量用完了

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int n = heights.length;
        int index = 0;

        while(index < n-1){
            if(heights[index] >= heights[index+1]){
                index++;
            }else{
                int need = heights[index+1] - heights[index];
                pq.offer(need);
                if(pq.size() > ladders){
                    bricks -= pq.poll();
                    if(bricks < 0) return index;
                }
                index++;
            }
        }
        return index;
    }
}

赏

谢谢你请我吃糖果

微信