目录
1. 在每个数行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
示例2：
输入: root = [1,2,3] 输出: [1,3]
提示：
- 二叉树的节点个数的范围是
[0,104] -231 <= Node.val <= 231 - 1
1.1 题目解析
题目本质：
把二叉树按“层”切片做统计。每一层只需要一个指标——最大值 → 典型的“层序遍历 + 层内聚合（max）”。
常规解法：
最直观就是 BFS 层序遍历：队列维护当前层节点，逐层弹出、收集该层的所有值，取最大后加入答案。
问题分析：
若“先把这一层所有值收集到临时数组/列表再求最大”，会产生不必要的额外空间与一次额外遍历。复杂度仍是 O(n)，但实现上可更简洁。另一个常见坑：层最大值的初始值不能写成 0——节点值可能为负数，必须用该层第一个节点或 Integer.MIN_VALUE 初始化。
思路转折：
在弹出节点时就顺手维护本层最大值，无需临时列表。每层循环开始把 max 置为 Integer.MIN_VALUE，遍历本层 size 个节点时不断 max = Math.max(max, cur.val)。这样一趟完成层序 + 统计。
1.2 解法
算法思想：
BFS 层序遍历。设当前队列大小为 size，表示本层节点数；用 max 记录本层最大值： 遍历 size 次：弹出节点 cur → max = max(max, cur.val) → 子节点入队。层结束把 max 进结果。
i）若 root == null，返回空列表。
ii）队列 q 入 root。
iii）当 q 非空：
记录 size = q.size()，max = Integer.MIN_VALUE。
循环 size 次：poll() 出本层节点，更新 max；其左右孩子非空则 offer()。
本层结束：result.add(max)。
iiii）返回 result。
易错点：
层最大值初始为 0 会错（全负层时错误），应使用 Integer.MIN_VALUE 或本层首节点值。
ArrayDeque 不允许存 null，但本题不会入队 null（先判空再入队）。
每层必须固定次数（size 次）弹出，否则会把下一层混进来。
别把 q.size() 写在循环条件里动态读取（会变化），要先保存为 size 再用。
1.3 代码实现
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size(); // 本层节点数（固定次数）
int max = Integer.MIN_VALUE; // 本层最大值初始化为整型最小
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll(); // 弹出本层一个节点
max = Math.max(max, cur.val); // 维护本层最大值
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
result.add(max); // 收录本层答案
}
return result;
}
}
复杂度分析：
- 时间复杂度：O(n)，每个节点仅入队出队各一次、比较一次。
- 空间复杂度：O(w)，w 为树的最大层宽（队列的峰值存量）；结果列表另占 O(h)（层数）存储输出。
2. 最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例：
输入：[2,7,4,1,8,1] 输出：1 解释： 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]， 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]， 接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]， 最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
2.1 题目解析
题目本质：
“多次取出当前两最大值并做替换”的过程 → 典型的最大堆（优先队列）模拟问题。
常规解法：
每回合对数组排序，取最大两个做运算，再把新值插回并继续排序。
问题分析：
每回合排序代价 O(n log n)，最坏要做 O(n) 回合，整体趋近 O(n² log n)，不够优雅。实际上我们只关心“反复取出最大两元素并插回”，这正是最大堆的强项：取最大 O(log n)，插入 O(log n)。
思路转折：
要想高效 → 用最大堆维护当前所有石头：
每回合 poll() 两次取最大；
若相等则都粉碎；若不等把差值 y-x 插回；
堆内元素随过程单调减少，最终剩 0 或 1 个。
复杂度降为 O(n log n)，实现也更简洁稳健。
2.2 解法
算法思想：
构建最大堆 pq：
重复：a = poll(), b = poll()；若 a != b 则 offer(a-b)；直到 pq.size() <= 1。结果为 pq.isEmpty() ? 0 : pq.peek()。
i）用大顶堆装入所有石头。
ii）当堆大小 ≥ 2：弹出两块最重的 a, b（约定 a ≥ b）。
iii）若 a > b，把差值 a-b 插回堆；若 a == b，两块都消失。
iiii）循环结束，堆空返回 0，否则返回堆顶。
易错点：
比较器建议用 Integer.compare(b, a)，避免极端值下的减法溢出（本题范围小也安全，习惯更好）。
a == b 时不要再插回 0（题意是两块完全粉碎，0 不应入堆）。
回合内必须先取两次再判断，不要边取边插导致逻辑混入。
边界：n=1 直接返回该石头；全部相等会逐步两两抵消。
2.3 代码实现
import java.util.*;
class Solution {
public int lastStoneWeight(int[] stones) {
// 最大堆：每次能 O(log n) 取/插最大值
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
for (int w : stones) pq.offer(w);
while (pq.size() > 1) {
int a = pq.poll(); // 最大
int b = pq.poll(); // 次大
if (a > b) {
pq.offer(a - b); // 只剩差值
} // a == b -> 两块都粉碎，不做任何事
}
return pq.isEmpty() ? 0 : pq.peek();
}
}
复杂度分析：
- 时间复杂度：O(n log n)。建堆 O(n)，每回合最多一次插入 O(log n)，回合数 ≤ n。
- 空间复杂度：O(n)，堆存放当前所有石头。