可以到达的最远建筑给你一个整数数组 heights 表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。你从建筑物 0 开始旅程不断向后面的建筑物移动期间可能会用到砖块或梯子。当从建筑物 i 移动到建筑物 i1下标 从 0 开始 时如果当前建筑物的高度 大于或等于 下一建筑物的高度则不需要梯子或砖块 如果当前建筑的高度 小于 下一个建筑的高度您可以使用 一架梯子 或(h[i1] - h[i]) 个砖块 如果以最佳方式使用给定的梯子和砖块返回你可以到达的最远建筑物的下标下标 从 0 开始 。https://leetcode.cn/problems/furthest-building-you-can-reach/?orderBymost_votes优先队列用 PriorityQueue 维护排在前 ladders 的高度差。当队列中元素超过梯子数量时 poll 最小元素对其使用砖块二分查找可能到达的楼房索引为【0,heights - 1】基于此使用二分查找找出可以到达的最大值/* * Copyright (c) Huawei Technologies Co., Ltd. 2023-2023. All rights reserved. */packagecom.huawei.prac;importjava.util.ArrayList;importjava.util.Collections;importjava.util.List;importjava.util.PriorityQueue;importjava.util.Queue;publicclassSolution4th{publicstaticvoidmain(String[]args){int[]heightsnewint[]{4,12,2,7,3,18,20,3,19};intbricks10;intladders2;System.out.println(furthestBuilding(heights,bricks,ladders));System.out.println(furthestBuildingNd(heights,bricks,ladders));}/** * 1642. 可以到达的最远建筑[贪心思想 优先队列 || 二分查找] * 用 PriorityQueue 维护排在前 ladders 的高度差。 * 当队列中元素超过梯子数量时 poll 最小元素对其使用砖块 * * param heights 楼房高度数组 * param bricks 砖块数量 * param ladders 梯子数量 * return 最远可达楼房的索引 */publicstaticintfurthestBuilding(int[]heights,intbricks,intladders){QueueIntegertopDifAscnewPriorityQueue();intdifHeight;for(inti0;iheights.length-1;i){difHeightheights[i1]-heights[i];if(difHeight0){topDifAsc.offer(difHeight);if(topDifAsc.size()ladders){bricks-topDifAsc.poll();}if(bricks0){returni;}}}returnheights.length-1;}/** * 二分查找可能到达的楼房索引为【0,heights - 1】 * 基于此使用二分查找找出可以到达的最大值 * * param heights 楼房高度数组 * param bricks 砖块数量 * param ladders 梯子数量 * return 最远可达楼房的索引 */publicstaticintfurthestBuildingNd(int[]heights,intbricks,intladders){intleft0;intrightheights.length-1;while(leftright){intmidright-(right-left)/2;if(canReach(heights,bricks,ladders,mid)){leftmid;}else{rightmid-1;}}returnleft;}privatestaticbooleancanReach(int[]heights,intbricks,intladders,intindex){ListIntegerdiffsnewArrayList();for(inti1;iindex;i){if(heights[i]heights[i-1]){diffs.add(heights[i]-heights[i-1]);}}Collections.sort(diffs);intneededBricks0;for(inti0;idiffs.size()-ladders;i){neededBricksdiffs.get(i);}returnneededBricksbricks;}}