大佬们来解答一下这个面试题（语言不限）

[cat404]

说有一个游戏战斗场景：左右两边各有一定数量战斗力不等（战斗力就是数组中的数值）的小兵，战斗开始的时候左边的小兵永远只会向右前进且不能回头，右边的小兵永远只会向左前进且不能回头，当两个小兵相遇的时高战斗力的小兵会把低战斗力的给淘汰掉。

现用一个数组来表示场上的所有小兵，其中正数代表左变的小兵，负数代表右边的小兵，然后实现一个函数输入这个输入返回战斗结果。

举例：

---

• 输入：[5, 10, -5]
• 结果：[5, 10]
• 解释：左边有战力分别为 5,10 的两个小兵，右边有一个战斗力为 5 的小兵，战斗开始的时候，5 和 10 向右一定，-5 向左移动，10 和-5 相遇，-5 小兵的战斗力是 5，被 10 淘汰掉，于是结果是 5,10

---

• 输入：[6, -6]
• 结果：[ ]
• 解释：左边有一个战斗力 6 的小兵，右边有一个战斗为 6 的小兵，战斗开始双方移动并相遇后因为战斗力相等均被淘汰

---

• 输入：[-1, -2, 3, -4, 5]
• 结果：[-1, -2, -4, 5]
• 解释：左边有 2 个小兵战斗力分别为 3,5，右边有 3 个小兵战斗力分别为 1,2,4 。战斗开始后-1 和-2 因为不能回头所以不会遇到敌方小兵，5 也同理。然后 3 和-4 相遇，3 被淘汰，所以结果是-1, -2, -4, 5

[azcvcza]

先找到数组中的一个正数，然后 slice 数组进行求和？

[azcvcza]

第一个

[MoYi123]

用栈模拟战斗过程，保存战死士兵的 index，然后输出就行了

[easonHHH]

@azcvcza #1 看[-1, -2, 3, -4, 5]

[easonHHH]

看了一下题目感觉可以用双指针解

[TomatoYuyuko]

设置一个窗口向右遍历，遇到负数就锁定并向左依次做对比，打得过就删除对应正数，打不过就删除负数窗口继续右移直到指向下一个负数

[goodboy95]

第二反应是建个栈，最后就倒序输出栈元素

[marquina]

leetcode 735，https://leetcode-cn.com/problems/asteroid-collision/

[zhjy23212]

stack，一个个推进去，比大小，复杂度 O(n)

[DJQTDJ]

public int[] test(int[] a) {
LinkedList<Integer> s = new LinkedList<>();
for (int i = 0; i < a.length; i++) {
if (a[i] > 0 || s.isEmpty() || s.getLast() < 0)
s.add(a[i]);
else if (s.getLast() <= -a[i])
if (s.pollLast() < -a[i]) i--;
}
return s.stream().mapToInt(i->i).toArray();
}

[lenqu]

C 的标准做法应该是双指针，还是挺简单的，毕竟不需要递归出最后的结果
其他语言，用俩个数组，执行一次就能出结果

[shilyx]

https://play.golang.org/p/E6BU5b6iOMn

[zifangsky]

我看了下，10L 兄弟的代码在逻辑上有点不太完善，你可以试试我这种写法（算法逻辑请参考注释部分）：
https://i.loli.net/2020/07/10/T94Rrce2nkJhwHV.png

[zifangsky]

有个地方逻辑有点问题，我改了一下：

//如果平局，则将其从存活数组移除，本次战斗结束
else if(lastItem == Math.abs(arr[i])){
survivors.remove(survivors.size() - 1);
rightWin = false;
break;
}

[xiaoming1992]

从右往左遍历正数，依次与其后的负数进行对比，正数小则移除正数，负数小则移除负数，最后剩下的就是所求

[index90]

对向移动，可以理解成一边静止，另一边单向移动。这样问题是不是变得更简单了？

[wolfzz]

(1)一个栈；
(2)数组从左到右遍历；
(3)如果栈顶为负，取出数为正, 判断胜负：
如果负数胜，继续取下一个数字 goto(2)；
如果正数胜，出栈,goto(3);
(4)其他情况： 把取出数入栈
把栈顺序输出即可

[phpcyy]

楼上的说的基本上是对的，我也是这个思路实现的

gist.github.com/phpcyy/283bc10742b89e9daa908fc2c1270820

[whileFalse]

简单。
首先，正数总是向右移动，负数总是向左移动。所以一旦负数达到最左边，它就不会遇到任何敌人；正数达到最右边就不会遇到任何敌人。
那么可以构建三个数组：
[负数逃逸区]、[战场]、[正数逃逸区]
一开始两个逃逸区是空的；战场就是输入数组。战斗结束后战场为空，两个逃逸区相加就是结果。

https://gist.github.com/Just4test/db4093ff0411df673f0206354ce9710f