LEETCODE 1642. Furthest Building You Can Reach 解题思路分析

题目大意：

可以到达的最远建筑

给你一个整数数组 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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1642

解题思路分析：

这道题第一反应是动态规划，毕竟是求最优解嘛，使用动态规划应该没毛病。但看了一下题目的数据规模，果断放弃了。对于这种数据量很大的题目，当不能使用DP时，我们要下意识想到贪心或者是二分。本题我们使用贪心来解题。

首先我们要想明白一个问题，梯子与砖块的区别在哪里？对于两栋建筑间的高度差diff，如果使用砖块，我们需要使用diff块，要使用梯子，无论diff为多大都只需1把，因此我们可以将梯子理解为无限多个砖块。这样一想，贪心思路就清晰了，假设我们有 n 架梯子，那么我们会在高度差diff 最大的那 n 次使用梯子，而在剩余的情况下使用砖块。

解题时，我们从下标0向后循环每一个高度，并使用PriorityQueue维护n个最大的高度差diff，对于剩余的diff，我们需要使用砖块，当砖块数量不够填平剩余的diff时，表示无法再继续移动，当前下标即是返回结果。

实现代码：

public int furthestBuilding(int[] heights, int bricks, int ladders) {
    // 优先队列中存储最大的ladders个高度差，这些差值将使用梯子
    PriorityQueue<Integer> q = new PriorityQueue<>();
    // 需要使用砖块的 高度 的和
    int sumHeight = 0;
    for(int i=0;i<heights.length-1;i++){ // 循环每一个高度
        int diff = heights[i+1] - heights[i]; // 当前与后一建筑的高度差
        if(diff>0){ // 如果高度差大于0
            q.offer(diff); // 将高度差加入优先队列
            // 如果优先队列已满，需要拿出一个其中的最小值，改为使用砖块
            if (q.size() > ladders) {  // 如果列队已满
                int minHeight = q.poll();  // 取出一个最小的高度差
                sumHeight += minHeight; // 将其累加至使用砖块的高度

            }
            // 如果需要使用砖块的高度大于砖块数量，表示不能继续前进
            if (sumHeight > bricks) { 
                return i; // 返回当前下标
            }
        }
    }
    return heights.length - 1;
}

本题解法执行时间为14ms。

Runtime: 14 ms, faster than 83.33% of Java online submissions for Furthest Building You Can Reach.

Memory Usage: 55.9 MB, less than 8.33% of Java online submissions for Furthest Building You Can Reach.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/1642-可以到达的最远建筑/