【面试高频题】热门数据结构面试题合集（堆）
本文正在参加「金石计划」
堆
堆一直是面试数据结构中的重中之重，今天通过 555 道与堆相关的题目来进行学习。
373. 查找和最小的K对数字
给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)(u,v)(u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk)(u_1,v_1), (u_2,v_2) ... (u_k,v_k)(u1,v1), (u2,v2) ... (uk,vk) 。
示例 1:
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
提示:
- 1<=nums1.length,nums2.length<=1041 <= nums1.length, nums2.length <= 10^41<=nums1.length,nums2.length<=104
- −109<=nums1[i],nums2[i]<=109-10^9 <= nums1[i], nums2[i] <= 10^9−109<=nums1[i],nums2[i]<=109
- nums1,nums2均为升序排列nums1, nums2 均为升序排列nums1,nums2均为升序排列
- 1<=k<=10001 <= k <= 10001<=k<=1000
基本分析
这道题和 (题解) 786. 第 K 个最小的素数分数 几乎是一模一样，先做哪一道都是一样的，难度上没有区别 🤣
最常规的做法是使用「多路归并」，还不熟悉「多路归并」的同学，建议先学习前置🧀：多路归并入门，里面讲述了如何从「朴素优先队列」往「多路归并」进行转换。
多路归并
令 nums1nums1nums1 的长度为 nnn，nums2nums2nums2 的长度为 mmm，所有的点对数量为 n∗mn * mn∗m。
其中每个 nums1[i]nums1[i]nums1[i] 参与所组成的点序列为：
由于 nums1nums1nums1 和 nums2nums2nums2 均已按升序排序，因此每个 nums1[i]nums1[i]nums1[i] 参与构成的点序列也为升序排序，这引导我们使用「多路归并」来进行求解。
具体的，起始我们将这 nnn 个序列的首位元素（点对）以二元组 (i,j)(i, j)(i,j) 放入优先队列（小根堆），其中 iii 为该点对中 nums1[i]nums1[i]nums1[i] 的下标，jjj 为该点对中 nums2[j]nums2[j]nums2[j] 的下标，这步操作的复杂度为 O(nlogn)O(n\log{n})O(nlogn)。这里也可以得出一个小优化是：我们始终确保 nums1nums1nums1 为两数组中长度较少的那个，然后通过标识位来记录是否发生过交换，确保答案的点顺序的正确性。
每次从优先队列（堆）中取出堆顶元素（含义为当前未被加入到答案的所有点对中的最小值），加入答案，并将该点对所在序列的下一位（如果有）加入优先队列中。
举个 🌰，首次取出的二元组为 (0,0)(0, 0)(0,0)，即点对 (nums1[0],nums2[0])(nums1[0], nums2[0])(nums1[0],nums2[0])，取完后将序列的下一位点对 (nums1[0],nums2[1])(nums1[0], nums2[1])(nums1[0],nums2[1]) 以二元组 (0,1)(0, 1)(0,1) 形式放入优先队列。
可通过「反证法」证明，每次这样的「取当前，放入下一位」的操作，可以确保当前未被加入答案的所有点对的最小值必然在优先队列（堆）中，即前 kkk 个出堆的元素必然是所有点对的前 kkk 小的值。
Java 代码：
class Solution {
boolean flag = true;
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> ans = new ArrayList<>();
int n = nums1.length, m = nums2.length;
if (n > m && !(flag = false)) return kSmallestPairs(nums2, nums1, k);
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->(nums1[a[0]]+nums2[a[1]])-(nums1[b[0]]+nums2[b[1]]));
for (int i = 0; i < Math.min(n, k); i++) q.add(new int[]{i, 0});
while (ans.size() < k && !q.isEmpty()) {
int[] poll = q.poll();
int a = poll[0], b = poll[1];
ans.add(new ArrayList<>(){{
add(flag ? nums1[a] : nums2[b]);
add(flag ? nums2[b] : nums1[a]);
}});
if (b + 1 < m) q.add(new int[]{a, b + 1});
}
return ans;
}
}
- 时间复杂度：令 MMM 为 nnn、mmm 和 kkk 三者中的最小值，复杂度为 O(M+k)×logM)O(M + k) \times \log{M})O(M+k)×logM)
- 空间复杂度：O(M)O(M)O(M)
二分
我们还能够使用多次「二分」来做。
假设我们将所有「数对和」按照升序排序，两端的值分别为 l=nums1[0]+nums2[0]l = nums1[0] + nums2[0]l=nums1[0]+nums2[0] 和 r=nums1[n−1]+nums2[m−1]r = nums1[n - 1] + nums2[m - 1]r=nums1[n−1]+nums2[m−1]。
因此我们可以在值域 [l,r][l, r][l,r] 上进行二分，找到第一个满足「点对和小于等于 xxx 的，且数量超过 kkk 的值 xxx」。
之所以能够二分，是因为 xxx 所在的点对和数轴上具有二段性：
- 点对和小于 xxx 的点对数量少于 kkk 个；
- 点对和大于等于 xxx 的点对数量大于等于 kkk 个。
判定小于等于 xxx 的点对数量是否大于等于 kkk 个这一步可直接使用循环来做，由于二分是从中间值开始，这一步不会出现跑满两层循环的情况。
当二分出第 kkk 小的值为 xxx 后，由于存在不同点对的点对和值相等，我们需要先将所有点对和小于等于 xxx 的值加入答案，然后酌情把值等于 xxx 的点对加入答案，知道满足答案数量为 kkk。
找值为 xxx 的所有点对这一步，可以通过枚举 nums1[i]nums1[i]nums1[i]，然后在 nums2nums2nums2 上二分目标值 x−nums1[i]x - nums1[i]x−nums1[i] 的左右端点来做。
最后，在所有处理过程中，我们都可以利用答案数组的大小与 kkk 的关系做剪枝。
Java 代码：
class Solution {
int[] nums1, nums2;
int n, m;
public List<List<Integer>> kSmallestPairs(int[] n1, int[] n2, int k) {
nums1 = n1; nums2 = n2;
n = nums1.length; m = nums2.length;
List<List<Integer>> ans = new ArrayList<>();
int l = nums1[0] + nums2[0], r = nums1[n - 1] + nums2[m - 1];
while (l < r) {
int mid = (int)(0L + l + r >> 1);
if (check(mid, k)) r = mid;
else l = mid + 1;
}
int x = r;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (nums1[i] + nums2[j] < x) {
List<Integer> temp = new ArrayList<>();
temp.add(nums1[i]); temp.add(nums2[j]);
ans.add(temp);
} else break;
}
}
for (int i = 0; i < n && ans.size() < k; i++) {
int a = nums1[i], b = x - a;
int c = -1, d = -1;
l = 0; r = m - 1;
while (l < r) {
int mid = (int)(0L + l + r >> 1);
if (nums2[mid] >= b) r = mid;
else l = mid + 1;
}
if (nums2[r] != b) continue;
c = r;
l = 0; r = m - 1;
while (l < r) {
int mid = (int)(0L + l + r + 1) >> 1;
if (nums2[mid] <= b) l = mid;
else r = mid - 1;
}
d = r;
for (int p = c; p <= d && ans.size() < k; p++) {
List<Integer> temp = new ArrayList<>();
temp.add(a); temp.add(b);
ans.add(temp);
}
}
return ans;
}
boolean check(int x, int k) {
int ans = 0;
for (int i = 0; i < n && ans < k; i++) {
for (int j = 0; j < m && ans < k; j++) {
if (nums1[i] + nums2[j] <= x) ans++;
else break;
}
}
return ans >= k;
}
}
- 时间复杂度：假设点对和的值域大小范围为 MMM，第一次二分的复杂度为 O((n×m)×logM)O((n \times m) \times \log{M})O((n×m)×logM)；统计点对和值小于目标值 xxx 的复杂度为 O(n×m)O(n \times m)O(n×m)；统计所有点对和等于目标值的复杂度为 O(max(n×logm,k))O(\max(n \times \log{m}, k))O(max(n×logm,k))（整个处理过程中利用了大小关系做了剪枝，大多循环都不会跑满，实际计算量会比理论分析的要低）
- 空间复杂度：O(k)O(k)O(k)
264. 丑数 II
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和 5 的正整数。
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
提示：
- 1<=n<=16901 <= n <= 16901<=n<=1690
基本思路
根据丑数的定义，我们有如下结论：
- 111 是最小的丑数。
- 对于任意一个丑数 xxx，其与任意的质因数（222、333、555）相乘，结果（2x2x2x、3x3x3x、5x5x5x）仍为丑数。
优先队列（小根堆）
有了基本的分析思路，一个简单的解法是使用优先队列：
- 起始先将最小丑数 111 放入队列
- 每次从队列取出最小值 xxx，然后将 xxx 所对应的丑数 2x2x2x、3x3x3x 和 5x5x5x 进行入队。
- 对步骤 2 循环多次，第 nnn 次出队的值即是答案。
为了防止同一丑数多次进队，我们需要使用数据结构 SetSetSet 来记录入过队列的丑数。
Java 代码：
class Solution {
int[] nums = new int[]{2,3,5};
public int nthUglyNumber(int n) {
Set<Long> set = new HashSet<>();
Queue<Long> pq = new PriorityQueue<>();
set.add(1L);
pq.add(1L);
for (int i = 1; i <= n; i++) {
long x = pq.poll();
if (i == n) return (int)x;
for (int num : nums) {
long t = num * x;
if (!set.contains(t)) {
set.add(t);
pq.add(t);
}
}
}
return -1;
}
}
- 时间复杂度：从优先队列中取最小值为 O(1)O(1)O(1)，往优先队列中添加元素复杂度为 O(logn)O(\log{n})O(logn)。整体复杂度为 O(nlogn)O(n\log{n})O(nlogn)
- 空间复杂度：O(n)O(n)O(n)
多路归并（多指针）
从解法一中不难发现，我们「往后产生的丑数」都是基于「已有丑数」而来（使用「已有丑数」乘上「质因数」222、333、555）。
因此，如果我们所有丑数的有序序列为 a1,a2,a3,...,ana1,a2,a3,...,ana1,a2,a3,...,an 的话，序列中的每一个数都必然能够被以下三个序列（中的至少一个）覆盖：
- 由丑数 ×2\times 2×2 所得的有序序列：1×21 \times 21×2、2×22 \times 22×2、3×23 \times 23×2、4×24 \times 24×2、5×25 \times 25×2、6×26 \times 26×2、8×28 \times 28×2 ...
- 由丑数 ×3 \times 3×3 所得的有序序列：1×31 \times 31×3、2×32 \times 32×3、3×33 \times 33×3、4×34 \times 34×3、5×35 \times 35×3、6×36 \times 36×3、8×38 \times 38×3 ...
- 由丑数 ×5\times 5×5 所得的有序序列：1×51 \times 51×5、2×52 \times 52×5、3×53 \times 53×5、4×54 \times 54×5、5×55 \times 55×5、6×56 \times 56×5、8×58 \times 58×5 ...
举个🌰，假设我们需要求得 [1,2,3,...,10,12][1, 2, 3, ... , 10, 12][1,2,3,...,10,12] 丑数序列 arrarrarr 的最后一位，那么该序列可以看作以下三个有序序列归并而来：
- 1×2,2×2,3×2,...,10×2,12×21 \times 2, 2 \times 2, 3 \times 2, ... , 10 \times 2, 12 \times 21×2,2×2,3×2,...,10×2,12×2 ，将 222 提出，即 arr×2arr \times 2arr×2
- 1×3,2×3,3×3,...,10×3,12×31 \times 3, 2 \times 3, 3 \times 3, ... , 10 \times 3, 12 \times 31×3,2×3,3×3,...,10×3,12×3 ，将 333 提出，即 arr×3arr \times 3arr×3
- 1×5,2×5,3×5,...,10×5,12×51 \times 5, 2 \times 5, 3 \times 5, ... , 10 \times 5, 12 \times 51×5,2×5,3×5,...,10×5,12×5 ，将 555 提出，即 arr×5arr \times 5arr×5
因此我们可以使用三个指针来指向目标序列 arrarrarr 的某个下标（下标 000 作为哨兵不使用，起始都为 111），使用 arr[下标]×质因数arr[下标] \times 质因数arr[下标]×质因数 代表当前使用到三个有序序列中的哪一位，同时使用 idxidxidx 表示当前生成到 arrarrarr 哪一位丑数。
Java 代码：
class Solution {
public int nthUglyNumber(int n) {
// ans 用作存储已有丑数（从下标 1 开始存储，第一个丑数为 1）
int[] ans = new int[n + 1];
ans[1] = 1;
// 由于三个有序序列都是由「已有丑数」*「质因数」而来
// i2、i3 和 i5 分别代表三个有序序列当前使用到哪一位「已有丑数」下标（起始都指向 1）
for (int i2 = 1, i3 = 1, i5 = 1, idx = 2; idx <= n; idx++) {
// 由 ans[iX] * X 可得当前有序序列指向哪一位
int a = ans[i2] * 2, b = ans[i3] * 3, c = ans[i5] * 5;
// 将三个有序序列中的最小一位存入「已有丑数」序列，并将其下标后移
int min = Math.min(a, Math.min(b, c));
// 由于可能不同有序序列之间产生相同丑数，因此只要一样的丑数就跳过（不能使用 else if ）
if (min == a) i2++;
if (min == b) i3++;
if (min == c) i5++;
ans[idx] = min;
}
return ans[n];
}
}
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(n)O(n)O(n)
313. 超级丑数
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
示例 1：
输入：n = 12, primes = [2,7,13,19]
输出：32
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
提示：
- 1 <= n <= 10610^6106
- 1 <= primes.length <= 100
- 2 <= primes[i] <= 1000
- 题目数据 保证 primes[i] 是一个质数
- primes 中的所有值都 互不相同 ，且按 递增顺序 排列
基本分析
根据丑数的定义，我们有如下结论：
- 111 是最小的丑数。
- 对于任意一个丑数 xxx，其与任意给定的质因数 primes[i]primes[i]primes[i] 相乘，结果仍为丑数。
优先队列（堆）
有了基本的分析思路，一个简单的解法是使用优先队列：
- 起始先将最小丑数 111 放入队列
- 每次从队列取出最小值 xxx，然后将 xxx 所对应的丑数 x∗primes[i]x * primes[i]x∗primes[i] 进行入队。
- 对步骤 222 循环多次，第 nnn 次出队的值即是答案。
为了防止同一丑数多次进队，我们可以使用数据结构 SetSetSet 来记录入过队列的丑数，但该做法常数较大，容易被卡。
利用题目规定的答案为 intintint 范围，以及丑数性质，我们可以直接在入队的时候做控制。
代码：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
PriorityQueue<Integer> q = new PriorityQueue<>();
q.add(1);
while (n-- > 0) {
int x = q.poll();
if (n == 0) return x;
for (int k : primes) {
if (k <= Integer.MAX_VALUE / x) q.add(k * x);
if (x % k == 0) break;
}
}
return -1; // never
}
}
- 时间复杂度：令 primesprimesprimes 长度为 mmm，需要从优先队列（堆）中弹出 nnn 个元素，每次弹出最多需要放入 mmm 个元素，堆中最多有 n∗mn * mn∗m 个元素。复杂度为 O(n∗mlog(n∗m))O(n * m \log{(n * m)})O(n∗mlog(n∗m))
- 空间复杂度：O(n∗m)O(n * m)O(n∗m)
多路归并
从解法一中不难发现，我们「往后产生的丑数」都是基于「已有丑数」而来（使用「已有丑数」乘上「给定质因数」primes[i]primes[i]primes[i]）。
因此，如果我们所有丑数的有序序列为 a1,a2,a3,...,ana1,a2,a3,...,ana1,a2,a3,...,an 的话，序列中的每一个数都必然能够被以下三个序列（中的至少一个）覆盖（这里假设 primes=[2,3,5]primes = [2,3,5]primes=[2,3,5]）：
- 由丑数 * 222 所得的有序序列：1∗21 * 21∗2、2∗22 * 22∗2、3∗23 * 23∗2、4∗24 * 24∗2、5∗25 * 25∗2、6∗26 * 26∗2、8∗28 * 28∗2 ...
- 由丑数 * 333 所得的有序序列：1∗31 * 31∗3、2∗32 * 32∗3、3∗33 * 33∗3、4∗34 * 34∗3、5∗35 * 35∗3、6∗36 * 36∗3、8∗38 * 38∗3 ...
- 由丑数 * 555 所得的有序序列：1∗51 * 51∗5、2∗52 * 52∗5、3∗53 * 53∗5、4∗54 * 54∗5、5∗55 * 55∗5、6∗56 * 56∗5、8∗58 * 58∗5 ...
我们令这些有序序列为 arrarrarr，最终的丑数序列为 ansansans。
如果 primesprimesprimes 的长度为 mmm 的话，我们可以使用 mmm 个指针来指向这 mmm 个有序序列 arrarrarr 的当前下标。
显然，我们需要每次取 mmm 个指针中值最小的一个，然后让指针后移（即将当前序列的下一个值放入堆中），不断重复这个过程，直到我们找到第 nnn 个丑数。
当然，实现上，我们并不需要构造出这 mmm 个有序序列。
我们可以构造一个存储三元组的小根堆，三元组信息为 (val,i,idx)(val, i, idx)(val,i,idx)：
- valvalval ：为当前列表指针指向具体值；
- iii ：代表这是由 primes[i]primes[i]primes[i] 构造出来的有序序列；
- idxidxidx：代表丑数下标，存在关系 val=ans[idx]∗primes[i]val = ans[idx] * primes[i]val=ans[idx]∗primes[i]。
起始时，我们将所有的 (primes[i],i,0)(primes[i], i, 0)(primes[i],i,0) 加入优先队列（堆）中，每次从堆中取出最小元素，那么下一个该放入的元素为 (ans[idx+1]∗primes[i],i,idx+1)(ans[idx + 1] * primes[i], i, idx + 1)(ans[idx+1]∗primes[i],i,idx+1)。
另外，由于我们每个 arrarrarr 的指针移动和 ansansans 的构造，都是单调递增，因此我们可以通过与当前最后一位构造的 ans[x]ans[x]ans[x] 进行比较来实现去重，而无须引用常数较大的 Set 结构。
代码：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int m = primes.length;
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]);
for (int i = 0; i < m; i++) {
q.add(new int[]{primes[i], i, 0});
}
int[] ans = new int[n];
ans[0] = 1;
for (int j = 1; j < n; ) {
int[] poll = q.poll();
int val = poll[0], i = poll[1], idx = poll[2];
if (val != ans[j - 1]) ans[j++] = val;
q.add(new int[]{ans[idx + 1] * primes[i], i, idx + 1});
}
return ans[n - 1];
}
}
- 时间复杂度：需要构造长度为 nnn 的答案，每次构造需要往堆中取出和放入元素，堆中有 mmm 个元素，起始时，需要对 primesprimesprimes 进行遍历，复杂度为 O(m)O(m)O(m)。整体复杂度为 O(max(m,nlogm))O(\max(m, n\log{m}))O(max(m,nlogm))
- 空间复杂度：存储 nnn 个答案，堆中有 mmm 个元素，复杂度为 O(n+m)O(n + m)O(n+m)
451. 根据字符出现频率排序
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
提示:
- 1<=s.length<=5×1051 <= s.length <= 5 \times 10^51<=s.length<=5×105
s由大小写英文字母和数字组成
数据结构 + 模拟
这是一道考察数据结构运用的模拟题。
具体做法如下：
- 先使用「哈希表」对词频进行统计；
- 遍历统计好词频的哈希表，将每个键值对以
{字符,词频}的形式存储到「优先队列（堆）」中。并规定「优先队列（堆）」排序逻辑为：- 如果
词频不同，则按照词频倒序； - 如果
词频相同，则根据字符字典序升序（由于本题采用 Special Judge 机制，这个排序策略随意调整也可以。但通常为了确保排序逻辑满足「全序关系」，这个地方可以写正写反，但理论上不能不写，否则不能确保每次排序结果相同）；
- 如果
- 从「优先队列（堆）」依次弹出，构造答案。
代码：
class Solution {
public String frequencySort(String s) {
char[] cs = s.toCharArray();
Map<Character, Integer> map = new HashMap<>();
for (char c : cs) map.put(c, map.getOrDefault(c, 0) + 1);
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{
return a[1] != b[1] ? b[1] - a[1] : a[0] - b[0];
});
for (char c : map.keySet()) q.add(new int[]{c, map.get(c)});
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
int[] poll = q.poll();
int c = poll[0], k = poll[1];
while (k-- > 0) sb.append((char)(c));
}
return sb.toString();
}
}
- 时间复杂度：令字符集的大小为 CCC。使用「哈希表」统计词频的复杂度为 O(n)O(n)O(n)；最坏情况下字符集中的所有字符都有出现，最多有 CCC 个节点要添加到「优先队列（堆）」中，复杂度为 O(ClogC)O(C\log{C})O(ClogC)；构造答案需要从「优先队列（堆）」中取出元素并拼接，复杂度为 O(n)O(n)O(n)。整体复杂度为 O(max(n,ClogC))O(\max(n, C\log{C}))O(max(n,ClogC))
- 空间复杂度：O(n)O(n)O(n)
数组实现 + 模拟
基本思路不变，将上述过程所用到的数据结构使用数组替代。
具体的，利用 ASCII 字符集共 128128128 位，预先建立一个大小为 128128128 的数组，利用「桶排序」的思路替代「哈希表」和「优先队列（堆）」的作用。
代码：
class Solution {
public String frequencySort(String s) {
int[][] cnts = new int[128][2];
char[] cs = s.toCharArray();
for (int i = 0; i < 128; i++) cnts[i][0] = i;
for (char c : cs) cnts[c][1]++;
Arrays.sort(cnts, (a, b)->{
return a[1] != b[1] ? b[1] - a[1] : a[0] - b[0];
});
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 128; i++) {
char c = (char)cnts[i][0];
int k = cnts[i][1];
while (k-- > 0) sb.append(c);
}
return sb.toString();
}
}
- 时间复杂度：令字符集的大小为 CCC，复杂度为 O(max(n,ClogC))O(\max(n, C\log{C}))O(max(n,ClogC))
- 空间复杂度：O(n+C+logC)O(n + C + \log{C})O(n+C+logC)
871. 最低加油次数
汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。
沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。
假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 111 英里就会用掉 111 升汽油。
当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。
为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 −1-1−1 。
注意：如果汽车到达加油站时剩余燃料为 000，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 000，仍然认为它已经到达目的地。
示例 1：
输入：target = 1, startFuel = 1, stations = []
输出：0
解释：我们可以在不加油的情况下到达目的地。
提示：
- 1<=target,startFuel,stations[i][1]<=1091 <= target, startFuel, stations[i][1] <= 10^91<=target,startFuel,stations[i][1]<=109
- 0<=stations.length<=5000 <= stations.length <= 5000<=stations.length<=500
- 0<stations[0][0]<stations[1][0]<...<stations[stations.length−1][0]<target0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target0<stations[0][0]<stations[1][0]<...<stations[stations.length−1][0]<target
贪心 + 优先队列（堆）
为了方便，我们记 target 为 t，记 startFuel 为 start，记 stations 为 ss。
我们可以模拟行进过程，使用 n 代表加油站总个数，idx 代表经过的加油站下标，使用 remain 代表当前有多少油（起始有 remain = start)，loc 代表走了多远，ans 代表答案（至少需要的加油次数）。
只要 loc < t，代表还没到达（经过）目标位置，我们可以继续模拟行进过程，每次将 remain 累加到 loc 中，含义为使用完剩余的油量，可以去到的最远距离，同时将所在位置 ss[idx][0] <= loc 的加油站数量加入优先队列（大根堆，根据油量排倒序）中，再次检查是否满足 loc < t（下次循环），此时由于清空了剩余油量 remain，我们尝试从优先队列（大根堆）中取出过往油量最大的加油站并进行加油（同时对加油次数 ans 进行加一操作），使用新的剩余油量 remain 重复上述过程，直到满足 loc >= t 或无油可加。
容易证明该做法的正确性：同样是消耗一次加油次数，始终选择油量最大的加油站进行加油，可以确保不存在更优的结果。
代码：
class Solution {
public int minRefuelStops(int t, int start, int[][] ss) {
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
int n = ss.length, idx = 0;
int remain = start, loc = 0, ans = 0;
while (loc < t) {
if (remain == 0) {
if (!q.isEmpty() && ++ans >= 0) remain += q.poll();
else return -1;
}
loc += remain; remain = 0;
while (idx < n && ss[idx][0] <= loc) q.add(ss[idx++][1]);
}
return ans;
}
}
- 时间复杂度：O(nlogn)O(n\log{n})O(nlogn)
- 空间复杂度：O(n)O(n)O(n)
总结
优先队列（堆）一直都是笔试/面试中的重点，而且考察的地方往往不在于手写堆，而是考察如何将原问题转换为能够使用优先队列（堆）来求解的问题。