尧图网页设计 
LeetCode 735. Asteroid Collision 小行星碰撞题解——LeetCode-Go 仓库栈模拟实战【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode 735 题「Asteroid Collision小行星碰撞」为对象结合开源仓库 LeetCode-Go 中 官方题解文档、Go 实现源码 与 单元测试完整拆解该题的题意、碰撞规则、栈模拟思路与代码细节。读完本文你将掌握「用单调栈处理一维方向性碰撞」的通用套路能够独立分析同源问题如 第 1047 题并理解如何用 Go 写出 O(n) 时间、O(n) 空间的简洁解法。题目描述给定一个整数数组asteroids表示排成一行的小行星。对于数组中每一个元素绝对值表示该行星的大小尺寸正负号表示移动方向正数向右移动负数向左移动所有行星以相同速度移动。要求找出所有碰撞结束后依然存在的小行星状态。碰撞规则如下两颗行星相遇时尺寸较小的一颗爆炸消失若两颗行星尺寸相同则双双爆炸移动方向相同的行星永远不会相遇。题目大意给定一个整数数组asteroids表示在同一行排列的行星。其中每个元素的正负号表示行星的移动方向正表示向右负表示向左绝对值表示行星的大小且所有行星速度相同。需要找出碰撞后剩下的所有行星。核心规则是两颗行星相互碰撞较小的行星爆炸大小相同时两颗都爆炸同向移动的行星永不碰撞。示例演示示例 1Input: asteroids [5, 10, -5] Output: [5, 10] Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.10 与 -5 相撞后 10 胜出5 与 10 同向永不碰撞。示例 2Input: asteroids [8, -8] Output: [] Explanation: The 8 and -8 collide exploding each other.8 与 -8 大小相同双双爆炸最终为空数组。示例 3Input: asteroids [10, 2, -5] Output: [10] Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.2 与 -5 相撞-5 胜出随后 10 与 -5 相撞10 胜出最终剩下[10]。示例 4Input: asteroids [-2, -1, 1, 2] Output: [-2, -1, 1, 2] Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.左侧两颗行星向左飞、右侧两颗向右飞永远无法相遇原样输出。约束条件数组长度最多为10000每个行星都是非零整数取值范围[-1000, 1000]。解题思路用栈模拟对对碰原文档明确指出这一题类似第 1047 题都是类似对对碰的消除游戏。区别在于 1047 题是相邻且相等才消除而本题是大行星吃掉小行星、同尺寸同归于尽。按照题意用栈模拟即可。考虑最终结果的形态可以归纳出以下关键事实源自 原题解文档所有向左飞的行星都向左所有向右飞的行星都向右向左飞的行星如果飞行途中没有向右飞行的行星那么它将安全穿过跟踪所有向右移动到右侧的行星最右边的一个将是第一个面对向左飞行行星碰撞的如果它幸存下来就继续前进否则之前任何向右的行星都会被逐一暴露出来参与碰撞。结论 3 是整道题的突破口由于只有「右行行星在左、左行行星在右」这种相邻关系才会碰撞因此只需要维护一个栈栈顶始终是当前最右侧的已处理行星。当新的行星向左飞来时它首先面对的就是栈顶那个向右飞行的行星。Go 源码精解逐行拆解栈实现仓库中 735. Asteroid Collision.go 给出了完整实现package leetcode func asteroidCollision(asteroids []int) []int { res : []int{} for _, v : range asteroids { for len(res) ! 0 res[len(res)-1] 0 res[len(res)-1] -v { res res[:len(res)-1] } if len(res) 0 || v 0 || res[len(res)-1] 0 { res append(res, v) } else if v 0 res[len(res)-1] -v { res res[:len(res)-1] } } return res }第一段内层循环持续吞并右行小行星for len(res) ! 0 res[len(res)-1] 0 res[len(res)-1] -v { res res[:len(res)-1] }这一段对应原文档解题思路中的「先处理这种情况一层循环把所有能碰撞的向右飞行的行星都碰撞完」。触发条件有三个必须同时满足len(res) ! 0栈非空res[len(res)-1] 0栈顶行星向右飞它会与向左飞的新行星迎面相遇res[len(res)-1] -v栈顶行星尺寸小于新行星尺寸。只要满足上述条件栈顶右行小行星就会被新来的左行行星撞毁res res[:len(res)-1]弹出栈顶。这个循环可能连续弹出多个右行行星——这正是原文档第 4 点「任何之前的向右的行星都会被逐一暴露出来碰撞」的代码体现。第二段三种入栈/出栈分支内层循环结束后分三种情况处理if len(res) 0 || v 0 || res[len(res)-1] 0 { res append(res, v) } else if v 0 res[len(res)-1] -v { res res[:len(res)-1] }情况 A直接入栈len(res) 0栈空新行星畅通无阻、或v 0新行星向右飞不会与任何左行栈顶碰撞、或res[len(res)-1] 0栈顶向左飞与新行星同向或背向永不碰撞。这对应原文档「如果栈顶行星向左飞新来的行星向右飞直接添加进来即可」的表述同时覆盖了更多同向场景。情况 B同归于尽v 0 res[len(res)-1] -v即栈顶向右飞且尺寸与新行星完全相同-v正是栈顶行星的尺寸。此时两者大小相同、双双爆炸弹出栈顶元素即可新行星也不入栈。为什么这样写是完备的从源码结构看代码没有显式处理「栈顶向右飞且尺寸大于新行星」的情况——这是因为此时新行星左行小行星会被栈顶撞毁直接丢弃即可不需要任何操作。三种结果新行星存活入栈、双方同归于尽、新行星被撞毁都被上面的分支完全覆盖逻辑闭环、无遗漏。测试用例验证仓库在 735. Asteroid Collision_test.go 中通过Test_Problem735覆盖了 6 组用例除了题目给出的 4 个示例外还额外补充了两个边界场景输入期望输出说明[5, 10, -5][5, 10]题目示例 1[8, -8][]题目示例 2同尺寸同归于尽[10, 2, -5][10]题目示例 3连环碰撞[-2, -1, 1, 2][-2, -1, 1, 2]题目示例 4永不碰撞[-1, -1, 1, -2][-1, -1, -2]追加用例左侧两个左行行星依次通过右侧 1 被 -2 撞毁[5, 8, -8][5]追加用例8 与 -8 同归于尽5 幸存其中[-1, -1, 1, -2]验证了「左行行星安全穿过」与「右行行星被逐一暴露碰撞」两个结论的组合场景-1, -1向左飞行直接入栈1向右飞行入栈-2飞来后先撞毁11 2随后栈顶为-1向左飞不满足碰撞条件-2直接入栈。运行验证方式仓库根目录的 gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部 leetcode 题解执行覆盖率测试在仓库根目录执行该脚本即可看到本题用例全部通过。复杂度分析从实现可以看出时间复杂度 O(n)每个行星至多入栈一次、出栈一次内层 while 循环弹出元素的总次数不超过入栈总次数空间复杂度 O(n)最坏情况下如示例 4 全部行星不碰撞栈中保留全部 n 个行星。这与仓库 PDF v1.7.97.md 的题解索引表中标注的O(n) / O(n)完全一致。题目难度为Medium。延伸与第 1047 题的异同原文档特别提示本题与 第 1047 题 Remove All Adjacent Duplicates In String 相似。两者的共同点是都用栈做「相邻消除」模拟、都是线性扫描核心差异在于消除触发条件1047 题栈顶字符与新字符相等即双双消除是同值互消735 题只有「栈顶右行、新来左行」才触发碰撞并且结果是「大者存活、小者消失、相等同灭」是大小比较后的胜负判定。理解这一对比就能把两道题归入同一个「栈 相邻消除条件」的思维模型面对类似问题时快速定位解法方向。仓库中对应题解文档见 1047 题解其 Go 实现同样位于leetcode/1047.Remove-All-Adjacent-Duplicates-In-String/目录下可对照阅读。总结小行星碰撞是经典的栈模拟应用题核心洞察在于碰撞只会发生在「右侧的右行行星」与「新来的左行行星」之间栈顶恰好代表当前最右侧的右行候选因此一次线性扫描加条件弹出即可完美模拟全部碰撞过程。LeetCode-Go 仓库为该题提供了 解题思路文档、可运行源码 和 完整测试同时网站版题解收录在 website/content/ChapterFour/0700~0799/0735.Asteroid-Collision.md是一份可直接研读与复用的完整素材。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 735. Asteroid Collision 小行星碰撞题解——LeetCode-Go 仓库栈模拟实战
LeetCode 735. Asteroid Collision 小行星碰撞题解——LeetCode-Go 仓库栈模拟实战【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode 735 题「Asteroid Collision小行星碰撞」为对象结合开源仓库 LeetCode-Go 中 官方题解文档、Go 实现源码 与 单元测试完整拆解该题的题意、碰撞规则、栈模拟思路与代码细节。读完本文你将掌握「用单调栈处理一维方向性碰撞」的通用套路能够独立分析同源问题如 第 1047 题并理解如何用 Go 写出 O(n) 时间、O(n) 空间的简洁解法。题目描述给定一个整数数组asteroids表示排成一行的小行星。对于数组中每一个元素绝对值表示该行星的大小尺寸正负号表示移动方向正数向右移动负数向左移动所有行星以相同速度移动。要求找出所有碰撞结束后依然存在的小行星状态。碰撞规则如下两颗行星相遇时尺寸较小的一颗爆炸消失若两颗行星尺寸相同则双双爆炸移动方向相同的行星永远不会相遇。题目大意给定一个整数数组asteroids表示在同一行排列的行星。其中每个元素的正负号表示行星的移动方向正表示向右负表示向左绝对值表示行星的大小且所有行星速度相同。需要找出碰撞后剩下的所有行星。核心规则是两颗行星相互碰撞较小的行星爆炸大小相同时两颗都爆炸同向移动的行星永不碰撞。示例演示示例 1Input: asteroids [5, 10, -5] Output: [5, 10] Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.10 与 -5 相撞后 10 胜出5 与 10 同向永不碰撞。示例 2Input: asteroids [8, -8] Output: [] Explanation: The 8 and -8 collide exploding each other.8 与 -8 大小相同双双爆炸最终为空数组。示例 3Input: asteroids [10, 2, -5] Output: [10] Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.2 与 -5 相撞-5 胜出随后 10 与 -5 相撞10 胜出最终剩下[10]。示例 4Input: asteroids [-2, -1, 1, 2] Output: [-2, -1, 1, 2] Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.左侧两颗行星向左飞、右侧两颗向右飞永远无法相遇原样输出。约束条件数组长度最多为10000每个行星都是非零整数取值范围[-1000, 1000]。解题思路用栈模拟对对碰原文档明确指出这一题类似第 1047 题都是类似对对碰的消除游戏。区别在于 1047 题是相邻且相等才消除而本题是大行星吃掉小行星、同尺寸同归于尽。按照题意用栈模拟即可。考虑最终结果的形态可以归纳出以下关键事实源自 原题解文档所有向左飞的行星都向左所有向右飞的行星都向右向左飞的行星如果飞行途中没有向右飞行的行星那么它将安全穿过跟踪所有向右移动到右侧的行星最右边的一个将是第一个面对向左飞行行星碰撞的如果它幸存下来就继续前进否则之前任何向右的行星都会被逐一暴露出来参与碰撞。结论 3 是整道题的突破口由于只有「右行行星在左、左行行星在右」这种相邻关系才会碰撞因此只需要维护一个栈栈顶始终是当前最右侧的已处理行星。当新的行星向左飞来时它首先面对的就是栈顶那个向右飞行的行星。Go 源码精解逐行拆解栈实现仓库中 735. Asteroid Collision.go 给出了完整实现package leetcode func asteroidCollision(asteroids []int) []int { res : []int{} for _, v : range asteroids { for len(res) ! 0 res[len(res)-1] 0 res[len(res)-1] -v { res res[:len(res)-1] } if len(res) 0 || v 0 || res[len(res)-1] 0 { res append(res, v) } else if v 0 res[len(res)-1] -v { res res[:len(res)-1] } } return res }第一段内层循环持续吞并右行小行星for len(res) ! 0 res[len(res)-1] 0 res[len(res)-1] -v { res res[:len(res)-1] }这一段对应原文档解题思路中的「先处理这种情况一层循环把所有能碰撞的向右飞行的行星都碰撞完」。触发条件有三个必须同时满足len(res) ! 0栈非空res[len(res)-1] 0栈顶行星向右飞它会与向左飞的新行星迎面相遇res[len(res)-1] -v栈顶行星尺寸小于新行星尺寸。只要满足上述条件栈顶右行小行星就会被新来的左行行星撞毁res res[:len(res)-1]弹出栈顶。这个循环可能连续弹出多个右行行星——这正是原文档第 4 点「任何之前的向右的行星都会被逐一暴露出来碰撞」的代码体现。第二段三种入栈/出栈分支内层循环结束后分三种情况处理if len(res) 0 || v 0 || res[len(res)-1] 0 { res append(res, v) } else if v 0 res[len(res)-1] -v { res res[:len(res)-1] }情况 A直接入栈len(res) 0栈空新行星畅通无阻、或v 0新行星向右飞不会与任何左行栈顶碰撞、或res[len(res)-1] 0栈顶向左飞与新行星同向或背向永不碰撞。这对应原文档「如果栈顶行星向左飞新来的行星向右飞直接添加进来即可」的表述同时覆盖了更多同向场景。情况 B同归于尽v 0 res[len(res)-1] -v即栈顶向右飞且尺寸与新行星完全相同-v正是栈顶行星的尺寸。此时两者大小相同、双双爆炸弹出栈顶元素即可新行星也不入栈。为什么这样写是完备的从源码结构看代码没有显式处理「栈顶向右飞且尺寸大于新行星」的情况——这是因为此时新行星左行小行星会被栈顶撞毁直接丢弃即可不需要任何操作。三种结果新行星存活入栈、双方同归于尽、新行星被撞毁都被上面的分支完全覆盖逻辑闭环、无遗漏。测试用例验证仓库在 735. Asteroid Collision_test.go 中通过Test_Problem735覆盖了 6 组用例除了题目给出的 4 个示例外还额外补充了两个边界场景输入期望输出说明[5, 10, -5][5, 10]题目示例 1[8, -8][]题目示例 2同尺寸同归于尽[10, 2, -5][10]题目示例 3连环碰撞[-2, -1, 1, 2][-2, -1, 1, 2]题目示例 4永不碰撞[-1, -1, 1, -2][-1, -1, -2]追加用例左侧两个左行行星依次通过右侧 1 被 -2 撞毁[5, 8, -8][5]追加用例8 与 -8 同归于尽5 幸存其中[-1, -1, 1, -2]验证了「左行行星安全穿过」与「右行行星被逐一暴露碰撞」两个结论的组合场景-1, -1向左飞行直接入栈1向右飞行入栈-2飞来后先撞毁11 2随后栈顶为-1向左飞不满足碰撞条件-2直接入栈。运行验证方式仓库根目录的 gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部 leetcode 题解执行覆盖率测试在仓库根目录执行该脚本即可看到本题用例全部通过。复杂度分析从实现可以看出时间复杂度 O(n)每个行星至多入栈一次、出栈一次内层 while 循环弹出元素的总次数不超过入栈总次数空间复杂度 O(n)最坏情况下如示例 4 全部行星不碰撞栈中保留全部 n 个行星。这与仓库 PDF v1.7.97.md 的题解索引表中标注的O(n) / O(n)完全一致。题目难度为Medium。延伸与第 1047 题的异同原文档特别提示本题与 第 1047 题 Remove All Adjacent Duplicates In String 相似。两者的共同点是都用栈做「相邻消除」模拟、都是线性扫描核心差异在于消除触发条件1047 题栈顶字符与新字符相等即双双消除是同值互消735 题只有「栈顶右行、新来左行」才触发碰撞并且结果是「大者存活、小者消失、相等同灭」是大小比较后的胜负判定。理解这一对比就能把两道题归入同一个「栈 相邻消除条件」的思维模型面对类似问题时快速定位解法方向。仓库中对应题解文档见 1047 题解其 Go 实现同样位于leetcode/1047.Remove-All-Adjacent-Duplicates-In-String/目录下可对照阅读。总结小行星碰撞是经典的栈模拟应用题核心洞察在于碰撞只会发生在「右侧的右行行星」与「新来的左行行星」之间栈顶恰好代表当前最右侧的右行候选因此一次线性扫描加条件弹出即可完美模拟全部碰撞过程。LeetCode-Go 仓库为该题提供了 解题思路文档、可运行源码 和 完整测试同时网站版题解收录在 website/content/ChapterFour/0700~0799/0735.Asteroid-Collision.md是一份可直接研读与复用的完整素材。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考