行星碰撞

为什么用栈?新来的负数只可能撞「最靠近它的那颗正数」,也就是栈顶;撞爆栈顶后它又面对新栈顶——这种「从最近的往里逐个结算」正是栈的拿手好戏。

起步 · 输入 [5,10,−5,−12]：上面一排是输入流,我们从左往右一颗一颗读。下面的栈装「还活着的行星」,现在是空的。

读 +5 · 正数直接入栈：第一颗 +5 向右飞。正数永远不会和「它左边、同样向右」的撞,所以直接入栈等着。

读 +10 · 同向不撞,入栈：+10 也向右。和栈顶 +5 同向,撞不着,继续入栈。栈现在是 [+5, +10]。

读 −5 · 撞栈顶 +10 被秒：来了 −5(向左),栈顶 +10(向右)相向要撞:|−5|=5 −5 自己爆掉,+10 纹丝不动,−5 没能进栈。栈还是 [+5, +10]。

读 −12 · 撞爆 +10,弹出：最后一颗 −12 撞栈顶 +10:|−12|=12 > 10,+10 被撞爆弹出。但 −12 还活着,要继续面对新栈顶 +5!

−12 再撞爆 +5：新栈顶 +5,−12 接着撞:12 > 5,+5 也被撞爆弹出,栈空了。前面再没有挡路的正数——要不要继续撞?

−12 安全落地 · 入栈：栈空、没有正数挡在前面,−12 一路畅通入栈。读完了!最终栈 = [−12],就是答案。回看:−5 被秒、−12 连撞爆 10 和 5 后自己活下来。

把这三种结局想清楚,这题的 while 就写对了。下面换几个小例子,专盯「等大同归于尽」「同向不撞」这两个边角。

例2 · 输入 [8,−8]：新例子 [8, −8],专看「等大同归于尽」。栈清空,从头读。

读 +8 · 正数入栈：先读 +8,正数入栈。

读 −8 · 等大,同归于尽：−8 撞栈顶 +8,大小完全相等。规则:一样大则两颗都爆——弹出 +8、−8 也不入栈,栈空,输出 []。这就是「相等」分支。

例3 · 输入 [10,2,−11]：再看 [10,2,−11],体会「负数弹完一个栈顶要继续撞下一个」的连环碰撞。栈清空,从头读。

读 +10 · 正数入栈：先 +10 入栈。

读 +2 · 同向入栈：+2 同向,入栈。栈 = [+10, +2]。

读 −11 · 先撞爆 +2：−11 撞栈顶 +2:11 > 2,+2 爆掉弹出。−11 还活着,继续撞新栈顶 +10。

−11 再撞爆 +10：新栈顶 +10:11 > 10,+10 也被撞爆,栈空。−11 还活着,前面再没正数挡路。

−11 安全落地：栈空、没有正数挡路,−11 入栈,输出 [−11]。一颗 −11 连弹了 +2、+10 才落地——这就是「弹完继续撞」。

例4 · 输入 [−2,−1,1,2]：最后看 [−2,−1,1,2]:负数全在左、正数全在右,专看「背向不撞」。栈清空,从头读。

读 −2 · 栈空,负数入栈：读 −2,栈空没有正数挡路,直接入栈。

读 −1 · 栈顶是负,同向不撞：−1 向左,栈顶 −2 也向左——同向,追不上,不撞,入栈。

读 +1 · 正数,直接入栈：+1 向右。当前是正数,根本不进碰撞循环(只有「负数撞正栈顶」才撞),入栈。

读 +2 · 同向入栈,全员存活：+2 入栈。整趟一次都没撞:左边的负数向左飞、右边的正数向右飞,背向越来越远。输出原样 [−2,−1,1,2]。

把「唯一触发条件」记死:只有正数挡在左边、来个负数,才相向。其余都直接入栈。

雷区实演 · 漏判「等大都爆」：假如代码只处理「栈顶小才弹」,忘了「等大也要弹」:−8 撞 +8 时既没弹 +8、−8 又被标记为撞不动停下——结果错误地留下 +8。正确应输出 []。

边界三连：先想清「背向不撞」「等大全爆」「连环撞」三种,代码就稳了。

面试追问：把「O(n) 摊还」和「为什么是栈顶」讲清楚,是这题面试的得分点。