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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/1642-可以到达的最远建筑/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。