1046.最后一块石头的重量
题目描述：
题目解析：
- 题意就是让我们拿出提供的数组的最大两个值，大减小作差，将差值再放入数组，直到数组空了或者只有一个元素为止。
解题思路：
- 题目要求我们在一个乱序的数组中找最大两个值，我们首先想到数组排序，但是由于我们还需要将差值放入数组，我们放一次就需要排序一次。
- 使用优先级队列，大根堆，开销会小一些，我们只需要每次拿堆顶元素即可。
算法代码：
public int lastStoneWeight(int[] stones) {
//创建大根堆
PriorityQueue<Integer> queue = new PriorityQueue<>(
(a,b) -> b - a
);
//入堆
for(int i = 0; i < stones.length; i++)
queue.offer(stones[i]);
//执行逻辑
while(!queue.isEmpty() && queue.size() != 1) {
int y = queue.poll();
int x = queue.poll();
queue.offer(y-x);
}
//返回值
return queue.isEmpty() ? 0 : queue.poll();
}295. 数据流的中位数
题目描述：
就是让我们实现一个类，有初始化，添加元素（每次添加一个），查看元素中位数
题目解析：
- 我们只需要每次拿取类中的元素的时候，能够直接拿到中位数即可。
- 我们可以使用两个堆，小根堆记录数的中位数之后的部分，大根堆记录中位数的前半部分。
- 这样当元素个数是偶数个的时候，我们直接拿到两个堆的堆顶元素即可。为奇数个元素的时候，直接取出堆元素多的那个的堆顶元素即可。
解题思路：
双堆法动态维护中位数的插入逻辑拆解
在处理动态数据的中位数时，常用「双堆配合」的技巧：一个 大根堆（堆顶是堆内最大数）和一个 小根堆（堆顶是堆内最小数），同时记录当前总元素个数。下面用最白话的方式，拆解插入新数据时的核心规则！
一、双堆分工：“左半” 和 “右半” 的容器
- 大根堆：存 “左半部分” 数据（可以理解为较小的一批数，堆顶是左半的最大值）。
- 小根堆：存 “右半部分” 数据（较大的一批数，堆顶是右半的最小值）。
- 核心目标：通过调整两堆的元素数量，让中位数能快速计算（奇数时取大根堆顶，偶数时取两堆顶的平均值）。
四、总结：规则绕，但逻辑通
这些规则看似复杂，核心只有一个：通过调整两堆的元素，维持 “偶数相等，奇数大根堆多 1” 的数量关系，让中位数能快速获取
三、插入后总数为奇数？让大根堆多 1 个
当插入新数后，总元素个数是奇数（比如原本 4 个，插入后 5 个），需要让 大根堆比小根堆多 1 个（这样中位数就是大根堆顶）。规则很简单：
新数比大根堆顶大：丢进小根堆（归到右半部分，不影响大根堆多 1 的结构）。 新数比大根堆顶小：丢进大根堆（归到左半部分，让大根堆数量 + 1，保持多 1 的状态）。
场景 2：新数比大根堆顶小（属于左半部分）
新数比左半的最大值还小，归到左半部分。同样看两堆数量：
若大根堆元素比小根堆多：先把大根堆顶（左半最大值）移到小根堆，再把新数丢进大根堆（大根堆数量不变，小根堆数量 + 1，最终两堆相等）。 若大根堆元素比小根堆少：直接把新数丢进大根堆（大根堆数量 + 1，最终两堆相等）。
二、插入后总数为偶数？平衡两堆数量
当插入新数后，总元素个数是偶数（比如原本 3 个，插入后 4 个），需要让两堆的元素数量 相等（这样中位数是两堆顶的平均数）。此时分两种场景：
场景 1：新数比大根堆顶大（属于右半部分）
新数比左半的最大值还大，自然归到右半部分。这时看两堆当前数量：
若大根堆元素比小根堆多：直接把新数丢进小根堆（大根堆原本多 1，丢进小根堆后，两堆数量相等）。 若大根堆元素比小根堆少：把小根堆顶（右半最小值）和新数比较，谁小就丢进大根堆，剩下的丢回小根堆（调整后两堆数量相等）。
解题代码：
//时间复杂度：O(LogN)
//空间复杂度：O(N)
class MedianFinder {
//列表中元素个数
int n = 0;
//大根堆记录前半部分值
PriorityQueue<Integer> big;
//小根堆记录后半部分值
PriorityQueue<Integer> little;
public MedianFinder() {
big = new PriorityQueue<>((a,b) ->{
return b-a;
});
little = new PriorityQueue<>();
}
public void addNum(int num) {
n += 1;
if(n == 1 ) {
big.offer(num);
return;
}
//元素个数为偶数，比前面的大
if(n % 2 == 0 && big.peek() <= num) {
//保持前后数据平衡
if(big.size() < little.size()) {
//比后面小
if(!little.isEmpty() && little.peek() >= num) {
big.offer(num);
}else {
int tmp = little.poll();
big.offer(tmp);
little.offer(num);
}
}else {
little.offer(num);
}
return;
}
//元素个数为偶数，比前面的小
if(n % 2 == 0 && big.peek() > num) {
//保持前后数据平衡
if(big.size() < little.size()) {
big.offer(num);
}else {
int tmp = big.poll();
big.offer(num);
little.offer(tmp);
}
return;
}
//元素个数为奇数,比前面小
if(n % 2 != 0 && big.peek() >= num) {
big.offer(num);
} else {
little.offer(num);
}
}
public double findMedian() {
if(n % 2 == 0) {
return (double)((big.peek() + little.peek())/ 2.0);
}
if(big.size() > little.size()) {
return big.peek();
} else {
return little.peek();
}
}
}