hot150-16-堆
...大约 28 分钟
难度说明：🟢简单🟡中等🔴困难
hot150-16-堆
🟡215-数组中的第K个最大元素
1.题目内容
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
2.题解思路
👻方法1：堆
大顶堆方案
思路分析：
- 大顶堆：数组元素依次入堆，堆顶元素始终指向最大的元素，若要拿到第
k个最大元素，则只需要弹出k-1个堆顶元素即可
/** * 215 数组中的第K个最大元素 */ public class Solution1 { // 大顶堆方法：数组元素依次入堆，遍历大顶堆元素，依次弹出栈顶元素，得到第K个即可 public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a); for (int num : nums) { heap.add(num); } // 弹出K-1个元素 for (int i = 1; i <= k - 1; i++) { heap.poll(); } return heap.peek(); // 第K大 } }复杂度分析
时间复杂度：O（n logN）（遍历N个元素，操作堆O（logN））
空间复杂度：O（N）维护一个N大小的大顶堆
小顶堆方案：维护一个大小为K的小顶堆，堆顶即为所求
- 小顶堆：维护一个存储
K个元素的小顶堆，初始化构建K个元素（堆顶始终指向当前最小的元素），从K+1开始依次和堆顶元素进行比较，如果比堆顶元素要大则替换（这个过程相当于逐步将小顶堆中的较小的元素给置换出来，最终遍历完成这个小顶堆中存放的就是K个最大值，基于此时堆顶元素就是第K大的元素）
/** * 215 数组中的第K个最大元素 */ public class Solution2 { /** * 小顶堆方法：维护一个K大小的小顶堆 * 1.先初始化小顶堆（K个元素） * 2.随后继续遍历后面的元素，如果元素大于当前的堆顶元素则进行置换（这个遍历过程会逐步将当前小顶堆中最小的元素置换出来，最终小顶堆中存放是K个最大的元素） * 3.遍历完成，最终小顶堆中存放是K个最大的元素，则此时堆顶元素就是第K大的元素 */ public int findKthLargest(int[] nums, int k) { // 初始化小顶堆 PriorityQueue<Integer> heap = new PriorityQueue<>(); // 初始化K个元素入堆 for(int i=0;i<k;i++){ heap.add(nums[i]); } // 继续遍历剩下的元素 for(int i=k;i<nums.length;i++){ // 判断当前遍历元素是否大于小顶堆堆顶元素，如果大于则进行置换，确保小顶堆中存放的是目前已遍历的最大的元素集合，逐步将最小值剔出 int cur = heap.peek(); if(nums[i]>cur){ heap.poll(); // 剔出堆顶元素 heap.add(nums[i]); // 补入新元素 } } return heap.peek(); // 第K大 } }- 大顶堆：数组元素依次入堆，堆顶元素始终指向最大的元素，若要拿到第
复杂度分析
时间复杂度：初始化堆O（k），遍历剩余元素可能需要进行堆操作（n-k）个元素 × O（logK）堆操作，总的时间复杂度：O(k + (n-k)log k) = O(n log k)
空间复杂度：O（K）始终维护一个大小为K的小顶堆
🔴502-IPO
1.题目内容
假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
答案保证在 32 位有符号整数范围内。
示例 1：
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
示例 2：
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6
2.题解思路
👻方法1：贪心+优先队列（堆）
思路分析：每次决策前，将项目启动资金不超多当前
w（初始资金）的任务加入优先队列（根据利润排序的大根堆），然后根据优先队列从最高利润的项目开始执行，逐步累加利润- 【1】题中给出的是净利润，因此此处将重心关注到能否启动项目？启动项目如何获得最大利润？
- 贪心思路：
- 初始的时候可以满足启动条件，后续
w不断累加，覆盖了这个启动条件（选择启动资金小于初始资金的项目），即初始的时候都可以启动，后续利润累加后也一定有条件启动，基于这个设定将满足启动条件的项目收集（升序排序）pros； - 题中给出的是净利润（不需要额外考虑成本消耗），因此既然满足了启动条件，后续只需要每次都摘利润最大的项目去做（大根堆维护），列出K个方案
- 在遍历列举K个方案的过程中如果没有发现可启动的
pros
- 初始的时候可以满足启动条件，后续
- 贪心思路：
/** * 502 IPO */ public class Solution1 { // 贪心 + 堆 public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) { int len = profits.length; // 项目个数 List<int[]> pros = new ArrayList<>(); // 将项目的启动资金和净利润组装到一起 for (int i = 0; i < len; i++) { pros.add(new int[]{capital[i], profits[i]}); } // 根据项目启动资金进行升序排序（capital） Collections.sort(pros, (a, b) -> a[0] - b[0]); // 根据list的每个数组组合元素的启动资金进行排序 // 根据项目净利润进行排序（profits），借助优先队列(大顶堆) PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a); int idx = 0; while (k > 0) { // 当项目列表存在可做的项目（idx未到数组尾部，且当前指向的项目启动资金<=w） while (idx < len && pros.get(idx)[0] <= w) { queue.offer(pros.get(idx)[1]); idx++; } if (queue.isEmpty()) break; // 没有可做的project w += queue.poll(); // 利润累加每次都拿最大利润的项目去做 k--; } return w; } }- 【1】题中给出的是净利润，因此此处将重心关注到能否启动项目？启动项目如何获得最大利润？
复杂度分析
时间复杂度：
空间复杂度：
👻方法2（🟢）：贪心+优先队列（堆：小顶堆动态维护暂时还不满足启动条件的项目，大顶堆动态维护可启动项目的利润集）
- 思路分析：基于方法1的优化，引入两个堆动态维护
- 优先队列设计
- 小顶堆
proQueue（维护本次决策暂时还不满足启动条件的项目集合（[项目启动资金，净利润]）） - 大顶堆
profitQueue（维护本次决策可启动的项目的利润集合，也可以理解为可启动的项目集合按照利润进行大顶堆排序（因为不需要记录项目信息，因此此处可以只关注利润最大值））
- 小顶堆
- 决策：K>0 需要选择项目执行（最多选择K个项目，因此如果出现不满足的情况可以理解为本轮轮空）
- 每一轮项目执行都会有利润的变化，而
w的变化会对下一轮的选择做出影响，因此在每一轮决策前都需要根据当前的w更新当前轮次可启动的项目的利润集合，从这些可启动的项目中选择利润最大的那个项目来执行 - 更新利润集：判断当前
proQueue中是否存在满足启动资金<=w的项目，存在则将其从proQueue移出并更新利润集（表示这个项目已经满足启动条件，可以加入到启动项目的利润集合中） - 选择项目：利润集更新完成，则需从当前可启动的项目中择选一个利润最大的项目（如果
profitQueue为空则说明当前没有满足启动条件的项目，因此本轮轮空直接break） - 更新W：如果择选出一个最优的可启动项目，则可更新w值，然后继续下一轮的择选
- 每一轮项目执行都会有利润的变化，而
- 优先队列设计
/**
* 502 IPO
*/
public class Solution2 {
// 贪心 + 堆（小顶堆维护项目，大顶堆维护利润）
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int len = profits.length; // 项目个数
List<int[]> pros = new ArrayList<>();
// 将项目的启动资金和净利润组装到一起
for (int i = 0; i < len; i++) {
pros.add(new int[]{capital[i], profits[i]});
}
// 借助优先队列（小顶堆）维护项目（按照启动资金capital进行排序）
PriorityQueue<int[]> proQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
// 根据项目净利润进行排序（profits），借助优先队列(大顶堆)
PriorityQueue<Integer> profitQueue = new PriorityQueue<>((a, b) -> b - a);
/**
* 项目选择有两个部分处理：一类是启动的时候就满足启动条件的项目，一类是启动的时候还暂时不满足启动条件的项目（后期随着w的累加可能会达到启动条件，需额外判断）
* 1.初始化：将启动资金满足<=w(起始资金)的项目装入profitQueue（可启动项目的利润集），其他项目排入proQueue（暂时还不满足启动条件的项目）
* - 引入堆概念，是为了优化操作效率，从堆顶获取到所需的要素
* 2.决策：因为每执行完一个项目，w就会随之改变，因此在选择下一个项目之前还需更新本次可启动选择的项目
* - 即每次执行决策之前，需要判断剩余的项目中是否有满足启动条件的项目，将其加入到利润集中供选择。随后从更新后的利润集中选择利润最大的项目执行
*/
// 1.初始化（划分可启动项目（利润集）、暂时还不满足启动条件的项目）
for (int i = 0; i < len; i++) {
if (pros.get(i)[0] <= w) {
profitQueue.add(pros.get(i)[1]); // 将初始时满足启动条件的项目载入利润集合（表示这些项目可以直接启动）
} else {
proQueue.add(pros.get(i)); // 剩余不满足初始化启动条件的项目则按照启动资金消耗载入小顶堆
}
}
// 2.决策：更新利润集、择选、更新利润
while (k > 0) {
// 每次执行决策前都需将满足启动条件的项目载入到profitQueue中（即更新profitQueue）
while (!proQueue.isEmpty() && proQueue.peek()[0] <= w) {
profitQueue.add(proQueue.poll()[1]);
}
// 从当前利润集中选择一个最大的项目执行(如果可执行项目为空，则跳过)
if (profitQueue.isEmpty()) {
break;
}
w += profitQueue.poll();
k--; // 一个项目选择完成，计数器-1
}
// 返回最大利润
return w;
}
}
🟡373-查找和最小的K对数字
1.题目内容
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 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]
示例 2:
输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
2.题解思路
👻方法1：堆（Top k 问题）
最小：小顶堆==（内存超出限制）==
/**
* 373 查找和最小的K对数字
*/
public class Solution2 {
/**
* 小顶堆
*/
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
// 构建小顶堆
PriorityQueue<List<Integer>> heap = new PriorityQueue<>(
// (list1,list2) -> ( list1.get(0) + list1.get(1)) - (list2.get(0) + list2.get(1))
Comparator.comparingInt(list -> (list.get(0) + list.get(1)))
);
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
List<Integer> temp = new ArrayList<>();
temp.add(nums1[i]);
temp.add(nums2[j]);
heap.add(temp);
}
}
List<List<Integer>> ans = new ArrayList<>();
// 和最小的K对数字
for(int i=0;i<k;i++){
ans.add(heap.poll());
}
// 返回结果
return ans;
}
}
复杂度分析
时间复杂度：O（mn logK） m、n分别为两个数组的长度
空间复杂度：O（mn）
最小：大顶堆思路（维护K个元素的大顶堆，遍历剩余元素，置换堆顶最大值，直到最终堆中保留最小的K个元素）（时间超出限制）
/**
* 373 查找和最小的K对数字
*/
public class Solution3 {
/**
* 大顶堆（维护K个元素的大顶堆，遍历剩余元素置换最大值，直到最终堆中保留K个最小元素）
*/
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
// 构建大顶堆
PriorityQueue<List<Integer>> heap = new PriorityQueue<>(
(list1, list2) -> (list2.get(0) + list2.get(1)) - (list1.get(0) + list1.get(1))
);
// 定义计数器
int count = 0;
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
List<Integer> temp = new ArrayList<>();
temp.add(nums1[i]);
temp.add(nums2[j]);
if (count < k) {
heap.add(temp); // 初始化大顶堆
} else {
// 超出K的部分需依次判断是否需要置换
List<Integer> cur = heap.peek();
if (cur.get(0) + cur.get(1) > nums1[i] + nums2[j]) {
heap.poll(); // 剔除堆顶元素
heap.add(temp); // 置换新元素
}
}
count++;
}
}
List<List<Integer>> ans = new ArrayList<>();
// 和最小的K对数字（大顶堆中保留即为所求）
while(!heap.isEmpty()){
ans.add(heap.poll());
}
// 返回结果
return ans;
}
}
🔴295-数据流的中位数
1.题目内容
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值
- 例如
arr = [2,3,4]的中位数是3 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5
实现 MedianFinder 类:
MedianFinder()初始化MedianFinder对象。void addNum(int num)将数据流中的整数num添加到数据结构中。double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 1：
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
2.题解思路
👻方法1：硬核法（排序）超时❌
硬核的思路在于：通过一个数组或者集合维护数据流元素，在插入过程中始终保证集合的有序性，随后获取中位数则可中规中矩直接根据集合元素个数是奇数还是偶数进行计算返回
- 乍一看就是维护一个数组或者集合，然后求其中位数（排序+获取中位数）。如果采用硬核维护的话需确保集合有序，可以在插入的时候进行控制
public class MedianFinder {
// 维护数组或集合元素
List<Integer> numList;
public MedianFinder() {
numList = new ArrayList<>();
}
public void addNum(int num) {
numList.add(num);
}
public double findMedian() {
// 遍历当前集合元素，获取中位数
int curLen = numList.size();
if (curLen == 0) {
return 0;
}
if (curLen == 1) {
return numList.get(0);
}
// 排序
Collections.sort(numList);
if (curLen % 2 == 0) {
// 偶数的中位数
return (numList.get(curLen / 2 - 1) + numList.get(curLen / 2)) / 2.0; // 注意int做除法的小数点问题
} else {
// 奇数的中位数
return numList.get(curLen / 2);
}
}
}
👻方法2：堆（🚀）动态维护最大堆和最小堆
思路分析：借助两个优先队列维护数据流元素，以中位数作为分界线处理
辅助集合（优先队列）
- leftQueue（大顶堆）：堆顶元素即为最大的元素（存储比较多的一半集合）
- rightQueue（小顶堆）：堆顶元素即为最小的元素（存储比较少的一半集合）
添加元素
- 思路1【堆顶元素判断】：比较当前元素和两个堆的堆顶元素，如果
curNum<=leftTop则放在leftQueue，如果curNum>rightTop则放在rightQueue（需做NPE处理），且每次补充一个新元素的同时需置换一个元素出来放到另一个队列中以保证元素的在两个集合的平衡 - 思路2【集合元素个数比较】🟢：比较当前两个集合元素个数，判断是奇数还是偶数以决定下一个数要放置的位置（通过这种思路巧妙的借助了堆的特性，又不需要进行堆顶元素判断）
- 相等说明为偶数，下一个数要放leftQueue（先将num放入rightQueue，然后取出rightQueue的堆顶元素放入leftQueue）
- 因为下一个数要放在A、B当中的某个集合，例如下一个数要放在A中，则需置换一个最大的元素出来（先插入A再获取A的堆顶元素即可完成），将置换出来的元素放到B以保证两个集合元素个数的平衡
- 不相等说明奇数，下一个数要放rightQueue（先将num放入leftQueue，然后取出leftQueue的堆顶元素放入rightQueue）
- 相等说明为偶数，下一个数要放leftQueue（先将num放入rightQueue，然后取出rightQueue的堆顶元素放入leftQueue）
- 思路1【堆顶元素判断】：比较当前元素和两个堆的堆顶元素，如果
/**
* 295 数据流的中位数
*/
public class MedianFinder {
/**
* 借助两个优先队列维护数据流元素，以中位数作为分界线处理
* 1.LessThanOrEqualToQueue（ leftQueue 存储小于等于中位数的元素）
* 2.MoreThanQueue（rightQueue 存储大于中位数的元素）
* - 添加元素(如果比较堆顶元素则需判空)
* - 思路1（比较堆顶元素）：如果 cur <= leftQueueTop(堆顶元素) 加入到leftQueue；如果 cur > rightQueue（小顶堆） 加入到rightQueue
* - 思路2（比较两个集合元素个数）：
* - 相等说明为偶数，下一个数要放leftQueue（先将num放入rightQueue，然后取出rightQueue的堆顶元素放入leftQueue）
* - 不相等说明奇数，下一个数要放rightQueue（先将num放入leftQueue，然后取出leftQueue的堆顶元素放入rightQueue）
*
* - 获取中位数（区分奇数、偶数）
* leftQueue（大顶堆）：堆顶元素即为最大的元素
* rightQueue（小顶堆）：堆顶元素即为最小的元素
*/
PriorityQueue<Integer> leftQueue;
PriorityQueue<Integer> rightQueue;
public MedianFinder() {
leftQueue = new PriorityQueue<>((x, y) -> (x - y)); // 小顶堆：存储比较多的一半集合
rightQueue = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆：存储比较少的一半集合
}
public void addNum(int num) {
if (leftQueue.size() == rightQueue.size()) {
// 当两个集合元素个数相等（偶数），需向leftQueue插入元素：将num插入rightQueue，然后将rightQueue的堆顶元素推到leftQueue
rightQueue.add(num);
leftQueue.add(rightQueue.poll());
} else {
// 当两个集合元素个数不相等（奇数），需向rightQueue插入元素：将num插入leftQueue，然后将leftQueue的堆顶元素推到rightQueue
leftQueue.add(num);
rightQueue.add(leftQueue.poll());
}
}
public double findMedian() {
// 如果两个队列个数相同则说明数据总数为偶数
if (leftQueue.size() == rightQueue.size()) {
return (leftQueue.peek() + rightQueue.peek()) / 2.0;
} else {
return leftQueue.peek();
}
}
}
复杂度分析
时间复杂度：
addNum：O（logN） 操作堆findMedian：O（1）操作堆（获取堆顶元素进行操作）
空间复杂度：O（N）优先队列的开销（N为数据流元素个数）
🔴004-寻找两个正序数组的中位数
1.题目内容
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
2.题解思路
👻方法1：模拟法（平展数组）
- 思路分析：基于模拟的思路，最基础的就是先将两个数组进行合并（【合并两个有序数组】），随后基于合并后的集合，根据集合元素个数的奇偶性来获取到中位数
/**
* 🔴 004 寻找两个正序数组的中位数 - https://leetcode.cn/problems/median-of-two-sorted-arrays/
*/
public class Solution1 {
/**
* 思路：暴力思路（将两个数组合为1个数组进行处理）
* ① 合并两个有序数组
* ② 返回合并后的数组的中位数
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// ① 合并两个有序数组
List<Integer> list = merge(nums1, nums2);
// ② 返回合并后的数组的中位数
int size = list.size();
if (size % 2 == 0) {
// return (list.get(size / 2) + list.get(size / 2 - 1)) / 2.0;
int left = 0, right = size - 1, mid = left + (right - left) / 2;
return (list.get(mid) + list.get(mid + 1)) / 2.0;
} else if (size % 2 == 1) {
return list.get(size / 2);
}
return -1;
}
/**
* 合并两个有序数组
* 思路1：循环条件取p1 < m || p2 < n，只有两个数组都遍历完成才跳出循环，在循环中处理边界条件
* 思路2：循环条件取p1 < m && p2 < n，当有一个数组遍历结束则跳出循环，跳出循环后处理尾部
*/
private List<Integer> merge(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
List<Integer> list = new ArrayList<>();
int p1 = 0, p2 = 0;
while (p1 < m || p2 < n) {
// 处理设置（处理数组边界问题）
int val1 = (p1 < m ? nums1[p1] : Integer.MAX_VALUE); // 注意此处如果是遇到边界不能简单取0，会导致OOM，因为处理条件导致指针不会移动引发无限循环（需处理好边界关系）
int val2 = (p2 < n ? nums2[p2] : Integer.MAX_VALUE);
if (val1 <= val2 && val1 != Integer.MAX_VALUE) {
list.add(val1);
p1++;
} else if (val2 < val1 && val2 != Integer.MAX_VALUE) {
list.add(val2);
p2++;
}
}
// 返回合并结果
return list;
}
}
复杂度分析
时间复杂度：O（m+n）m、n分别为两个数组的元素个数
空间复杂度：O（m+n）需要构建辅助集合存储有序合并后的元素
👻方法2：堆
- 思路分析：参考上述【295-数据流的中位数】，类似的可以构建辅助堆来处理排序关系
- ① 构建leftQueue（大顶堆）、rightQueue（小顶堆）维护所有元素，这两个堆衔接起来构成一个有序的序列
- ② 初始化堆：根据当前堆中元素个数差值来决定当前遍历num的入堆处理：此处处理的设计巧妙之处在于充分利用堆的特性和置换思路，而不用自行手动做各种封装比较
leftSize == rightSize：当前总元素个数为偶数个，则num需要插入到leftQueue。此处采用置换的思路，先将元素num插入rightQueue，然后将排序后的rightQueue的堆顶元素置换出来放到leftQueueleftSize != rightSize：当前总元素个数为奇数个，则num需要插入到rightQueue。同理，此处先将元素num插入leftQueue，然后将排序后的leftQueue的堆顶元素置换出来放到rightQueue
- ③ 基于处理好的堆，此时leftQueue 和 rightQueue 的堆顶元素恰好对应着中位数的关键，根据元素总数的奇偶性处理即可
- 常见问题分析：
- 此处可能会陷入如何确保处理后的两个堆衔接的有序性
/**
* 🔴 004 寻找两个正序数组的中位数 - https://leetcode.cn/problems/median-of-two-sorted-arrays/
*/
public class Solution2 {
/**
* 思路：堆思路（维护一个大顶堆(left)和一个小顶堆(right)）
* 大顶堆（left）：存储[0,mid]的元素
* 小顶堆（right）：存储[mid+1,size-1]的元素
* 如果元素总和为偶数则两个堆的大小是一样的，如果元素总和为奇数则left堆比right堆多1个元素
* 整体思路构建如下：参考295-数据流的中位数处理思路
* ① 构建leftQueue（大顶堆）、rightQueue（小顶堆）维护所有元素，这两个堆衔接起来构成一个有序的序列
* ② 初始化堆：根据当前堆中元素个数差值来决定当前遍历num的入堆处理：
* - leftSize == rightSize：当前总元素个数为偶数个，则num需要插入到leftQueue。此处采用置换的思路，先将元素num插入rightQueue，然后将排序后的rightQueue的堆顶元素置换出来放到leftQueue
* - leftSize != rightSize：当前总元素个数为奇数个，则num需要插入到rightQueue。同理，此处先将元素num插入leftQueue，然后将排序后的leftQueue的堆顶元素置换出来放到rightQueue
* - 此处处理的设计巧妙之处在于充分利用堆的特性和置换思路，而不用自行手动做各种封装比较
* ③ 基于处理好的堆，此时leftQueue 和 rightQueue 的堆顶元素恰好对应着中位数的关键，根据元素总数的奇偶性处理即可
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// ① 定义小顶堆、大顶堆维护元素信息
PriorityQueue<Integer> leftQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1; // 左侧大顶堆
}
});
PriorityQueue<Integer> rightQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2; // 右侧小顶堆
}
});
// ② 遍历元素（根据当前堆元素的数量差来处理载入元素）
int m = nums1.length, n = nums2.length;
for (int i = 0; i < m; i++) {
addNum(leftQueue, rightQueue, nums1[i]);
}
for (int j = 0; j < n; j++) {
addNum(leftQueue, rightQueue, nums2[j]);
}
// ③ 根据排序好的堆元素的奇偶来获取中位数
if ((m + n) % 2 == 0) {
return (leftQueue.peek() + rightQueue.peek()) / 2.0;
} else if ((m + n) % 2 == 1) {
return leftQueue.peek();
}
return -1;
}
// 处理元素
private void addNum(PriorityQueue<Integer> leftQueue, PriorityQueue<Integer> rightQueue, int num) {
// 根据当前左、右堆的元素个数来处理
if (leftQueue.size() == rightQueue.size()) {
// 当两个集合元素个数相等（偶数），需要向leftQueue插入元素：将元素num插入到rightQueue，随后将rightQueue的堆顶元素置换到leftQueue（以此确保left始终比right多一个元素）
rightQueue.offer(num);
leftQueue.offer(rightQueue.poll());
} else {
// 当两个即可元素个数不相等（奇数），需要向rightQueue插入元素：将元素num插入到leftQueue，随后将leftQueue的堆顶元素置换到rightQueue
leftQueue.offer(num);
rightQueue.offer(leftQueue.poll());
}
}
}
复杂度分析
时间复杂度：O（m+n）m、n分别为两个数组的元素个数
空间复杂度：O（m+n）需要构建辅助集合(两个堆)存储有序合并后的元素
🔴239-滑动窗口最大值
1.题目内容
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
2.题解思路
👻方法1：暴力法-区间统计（❌超时限制）
- 思路分析：从起点开始遍历（确定每个区间【left，right】），每次都去计算一遍区间的最大值，然后存储
/**
* 239 滑动窗口的最大值
*/
public class Solution1 {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
// 1.定义数组存储滑动窗口的最大值
int[] maxArr = new int[len - k + 1]; // maxArr[i] 表示以i为起点的滑动窗口的最大值
// 2.暴力循环（确定窗口起点和终点，获取滑动窗口的最大值）
for (int i = 0; i < len - k + 1; i++) { // i 的临界取值受限于滑动窗口大小
// 统计区间的最大值
int curMax = Integer.MIN_VALUE;
for (int left = i; left < i + k; left++) {
curMax = Math.max(curMax, nums[left]); // 更新最大值
}
maxArr[i] = curMax; // 填充数组
}
// 返回结果集
return maxArr;
}
}
复杂度分析
时间复杂度：O（n2）（需遍历数组的同时还需计算滑动窗口的最大值）
空间复杂度：O（m） （m<n）构建辅助数组存储滑动窗口的最大值
👻方法2：堆（优先队列）
- 思路分析：借助堆实时维护最大值（大顶堆可以实时维护一系列元素中的最大值）
- （1）大根堆定义：将数组元素和对应索引构建成数组，维护大根堆（数据元素不相等时优先按照元素大小排序，数据元素相等时优先按照索引大小排序）
- （2）初始化大根堆：初始化窗口（前k个元素入堆），此时初始化窗口的最大值对应的就是堆顶元素
- （3）遍历剩余元素，滑动窗口，更新最大值
cur为max数组当前填充位置（实际也可以理解为当前窗口的左边界）每次遍历新的元素直接将其入堆，随后判断堆顶元素对应索引是否小于
cur（如果小于则表示这个堆顶元素已经是左边界左侧的内容了，已经划出了窗口，可以直接移除）- 如果小于则直接移除（
poll，除了此处移除，其他情况用peek查看元素），当堆顶元素（最大值出现在窗口内，则停止移出操作，此时堆顶元素对应为窗口的最大值）
- 如果小于则直接移除（
上述操作完成，此时堆顶元素对应的就是当前窗口的最大值
以此类推，遍历完所有元素，最终返回封装好的
max
/**
* 🔴 239 滑动窗口的最大值 - https://leetcode.cn/problems/sliding-window-maximum/description/
*/
public class Solution2 {
/**
* 思路：堆（借助堆始终维护当前限定范围的最大值）
* ① 维护k个元素的大顶堆（滑动窗口），堆顶元素指向当前的最大值（排序规则：优先元素大小，其次索引先后）
* ② 遍历剩余元素，滑动窗口，更新最大值。定义 cur 指向指向当前max[]最值封装位置（也是滑动窗口左边界的位置）
* - （1）新元素入堆
* - （2）根据cur与当前堆顶元素（top,topIdx）的索引位置进行比较，检验当前堆顶元素是否在滑动窗口中
* - 2.1 topIdx<cur,说明该元素不在滑动窗口内，需要将元素不断移出，直到最值出现在滑动窗口内，记录最值，然后继续下一步遍历
* - 此处堆的移出操作是针对堆顶元素不在滑动窗口限定范围内的情况，其他情况都是查看元素（处理最值不代表要将其移出，因为窗口滑动后当前取到的这个最值可能还是在限定范围内）
*/
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
// 定义结果集
int[] max = new int[n - k + 1];
// ① 维护K个元素的大顶堆（排序规则：优先元素大小，其次索引先后）
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] != o2[0] ? o2[0] - o1[0] : o1[1] - o2[1]; // 数据类型：int[]{itemVal,itemIdx}
}
});
// 构建大根堆
for (int i = 0; i < k; i++) {
priorityQueue.offer(new int[]{nums[i], i});
}
int cur = 0; // cur指向当前窗口左边界（也是max[]数组填充位置）
// 取出当前第1个窗口位置下的最大值
max[cur++] = priorityQueue.peek()[0]; // 此处仅仅是读取数值（因为这个最值可能在后面的滑动过程中还会用到）
// ② 遍历剩余元素，滑动窗口
for (int i = k; i < n; i++) {
// 新元素入堆
priorityQueue.offer(new int[]{nums[i], i});
// 校验cur（窗口左边界）与堆顶元素索引的关系
while (priorityQueue.peek()[1] < cur) {
// 当前堆顶元素不在窗口覆盖范围，需依次弹出，直到找到在窗口范围内的堆顶元素
priorityQueue.poll();
}
// 当堆顶元素出现在窗口覆盖范围内，记录这个最值
max[cur++] = priorityQueue.peek()[0];
}
// 返回最终结果
return max;
}
public static void main(String[] args) {
int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7}; // [3,3,5,5,6,7]
Solution2 solution = new Solution2();
int[] res = solution.maxSlidingWindow(nums, 3);
PrintUtil.print(res);
}
}
复杂度分析
- 时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)
空间复杂度：O(n)，即为优先队列需要使用的空间（一般计算的是额外的使用空间，结果集存储空间另作讨论）
Powered by Waline v3.1.3