1. //给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。 
  2. //
  3. // 你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。 
  4. //
  5. // 当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时： 
  6. //
  7. // 
  8. // 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块 
  9. // 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块 
  10. // 
  11. //如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
  12. //
  13. // 
  14. //
  15. // 示例 1： 
  16. //
  17. // 
  18. //输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
  19. //输出：4
  20. //解释：从建筑物 0 出发，你可以按此方案完成旅程：
  21. //- 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
  22. //- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
  23. //- 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
  24. //- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
  25. //无法越过建筑物 4 ，因为没有更多砖块或梯子。
  26. // 
  27. //
  28. // 示例 2： 
  29. //
  30. // 
  31. //输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
  32. //输出：7
  33. // 
  34. //
  35. // 示例 3： 
  36. //
  37. // 
  38. //输入：heights = [14,3,19,3], bricks = 17, ladders = 0
  39. //输出：3
  40. // 
  41. //
  42. // 
  43. //
  44. // 提示： 
  45. //
  46. // 
  47. // 1 <= heights.length <= 105 
  48. // 1 <= heights[i] <= 106 
  49. // 0 <= bricks <= 109 
  50. // 0 <= ladders <= heights.length 
  51. // 
  52. // Related Topics 堆 二分查找 
  53. // 👍 14 👎 0

一道周赛第三题，比赛的时候强行递归超时。以目前的位置，剩余砖块，剩余梯子做记忆化搜索空间爆了。就没做出来。
因为每个梯子无论多高的间隔都可以以一个梯子渡过，而砖块缺多少高度就要垫多少个。
因此这题需要尽量在间隔大的建筑之间使用梯子，在间隔小的建筑使用砖头。

贪心，用梯子搭间隔最大的建筑

这个思路的特点就是，假设路过的建筑可以随时瞬移回去。
在路过的时候优先使用砖头垫上去，发现砖头不够的时候使用时空穿梭，将间隔最大的建筑那里垫的砖头换成梯子。
这样手里的砖头就多了出来，可以放在其他间隔较小的地方。

  2. class Solution {
  4.     public int furthestBuilding(int[] heights, int bricks, int ladders) {
  5.         PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
  6.             @Override
  7.             public int compare(Integer o1, Integer o2) {
  8.                 return o2 - o1;
  9.             }
  10.         });
  11.         int i = 1;
  12.         for (; i < heights.length; i++) {
  13.             // 如果可以直接过，不需要搭梯子
  14.             if (heights[i] <= heights[i-1]){
  15.                 continue;
  16.             }
  18.             // 需要搭高diff过
  19.             int diff = heights[i] - heights[i - 1];
  20.             // 优先使用砖头搭过去
  21.             if (bricks >= diff){
  22.                 bricks -= diff;
  23.                 queue.offer(diff);
  24.             }else {
  25.                 // 砖头不够搭了
  26.                 // 如果还有梯子，使用梯子搭过去
  27.                 if (ladders > 0){
  28.                     ladders --;
  29.                     // 之前垫的最多的砖头
  30.                     Integer preMaxDiff = queue.isEmpty() ? -1 : queue.peek();
  31.                     // 如果之前垫的砖头比现在多
  32.                     // 回去把梯子换成之前的砖头
  33.                     if (preMaxDiff > diff){
  34.                         // 原来的砖头已经换成梯子了
  35.                         // 剩余的砖头数量增加了
  36.                         bricks += queue.poll();
  37.                         // 用砖头垫过当前这个建筑
  38.                         bricks -= diff;
  39.                     }
  40.                     // 如果现在这个距离是更大的，直接用梯子过即可
  41.                 }else {
  42.                     // 此时梯子也用完了， 已经没法到达i了
  43.                     return i - 1;
  44.                 }
  45.             }
  46.         }
  47.         // 到这里说明已经爬到了最后一个建筑，此时i多加了一次
  48.         return i - 1;
  49.     }
  50. }

二分

二分法总是很容易理解，但是比赛的时候就是想不起来。
二分的思路是，要求一个能到达的最值，那么二分的去找这个值。
选定一个值之后，看看利用给定的砖头和梯子能否达到这个值。
如果可以达到，说明答案至少也是这个数，而且还可以再往后找找还有没有更大的。
如果不能达到，说明这个值以后所有的数也不能达到，那就往前找找什么时候可以到达。


class Solution {


    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int left = 0;
        int right = heights.length - 1;

        int res = 0;
        while (left <= right){
            int mid = (left + right) / 2;
            // 如果能到mid，试试能不能往后走走
            if (check(heights, mid, bricks, ladders)){
                left = mid + 1;
                res = mid;
            }else {
                // 如果mid都不能到，往前搜索
                right = mid - 1;
            }
        }
        return res;
    }

    // 如果目的是target，现有bricks个砖块和ladders个梯子，检查能否到达
    public boolean check(int[] height, int target, int bricks, int ladders){
        int[] diffs = new int[target + 1];
        for (int i = 1; i < target + 1; i++) {
            diffs[i] = height[i] - height[i - 1];
        }
        // 目的是到达target， diffs记录的是所有需要解决的间隔
        // 将间隔排序
        Arrays.sort(diffs);
        // 先将大间隔解决
        for (int i = diffs.length - 1; i >= 0; i--) {
            // 如果不需要搭梯子
            if (diffs[i] <= 0){
                continue;
            }
            // 优先使用梯子搭过去
            if (ladders > 0){
                ladders --;
            }else {
                // 如果梯子不够再使用砖头
                // 如果砖头不够用，直接返回false，说明不可到达
                if (bricks < diffs[i]){
                    return false;
                }
                bricks -= diffs[i];
            }
        }
        return true;
    }
}