Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列特别篇 - 官方小活动 『30-Day LeetCoding Challenge』。
这里是 4 月 12 号的题，也是题目列表中的第 1046 题 -- 『最后一块石头的重量』
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 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
EASY
看起来描述挺长，但其实就是一个大值依次互相抵消求最后剩余的小游戏。小猪没有想到什么数学方式，所以就正常的根据游戏流程来求最终结果吧。
由于数字是无序的，所以我们先进行一个排序。然后按照游戏流程，把两个最大值进行抵消，如果存在余量则通过插入排序的方式放入合适的位置。这样直到最后剩余 0 个或者 1 个数字，便得到了结果。
具体代码如下：
const lastStoneWeight = stones => {
stones.sort((a, b) => a - b);
while (stones.length > 1) {
const x = stones.pop();
const y = stones.pop();
if (x === y) continue;
const d = Math.abs(x - y);
let idx = stones.length;
while (idx > 0) {
if (stones[idx - 1] <= d) break;
stones[idx] = stones[idx - 1];
--idx;
}
stones[idx] = d;
}
return stones.length === 1 ? stones[0] : 0;
};上面的方案最开始使用了一个全局的排序，随后在遍历中也对余量使用了一次基于遍历的插入行为。那么这里优化方案非常明显，我们可以优化排序的方式，从而简化整个流程。
由于输入数据的范围是 [1, 1000]，所以我们可以非常轻松的用桶排序来完成最初的排序，并且后续的余量处理也会变得更加容易。具体代码如下：
const lastStoneWeight = stones => {
const buckets = new Uint8Array(1001);
let t = 0;
for (const val of stones) ++buckets[val];
for (let i = 1000; i > 0; --i) {
if (!buckets[i]) continue;
if (!t) { buckets[i] % 2 && (t = i); continue; }
const d = Math.abs(t - i);
t = d >= i ? d : (++buckets[d], 0);
--buckets[i++];
}
return t;
};又是一个基于桶排序完成的优化，在特定的场景下还是『真香』的。希望能帮助到有需要的小伙伴。
如果觉得不错的话，记得『三连』哦。小猪爱你们哟~
