P2604. 荒岛求生

解题思路

注意，本题和 行星碰撞 几乎完全一致。唯一的区别在于，本题出现体力不相等的情况，需要进行 减法操作 而不是直接的 吞并操作。

题意理解以及栈模拟思路的总框架

首先需要理解题意，题目中数字的正负性代表的含义：正数表示向右移动，负数表示向左移动。 以示例一为例，可以用下图来表示：

从上图可以看出，上述两个最先相遇的 8 和 -8 会进行匹配，并且决出胜负结果。 这个过程实际上和 有效的括号 这类括号配对问题非常类似，只不过是从括号配对换成了 向左的数字和最近的向右数字进行匹配。

可以将向右的数字类比成 左括号，向左的数字类比成 右括号，来进行数字匹配的思考。 很显然也应该考虑 栈 来完成本题目。整体的代码框架如下：

向右数字的处理

遇到向右的数字的时候，非常好处理，直接入栈即可。 因为遇到一个向右数字的时候，即使栈中存在一些向左移动的人，他们是 背向移动 的，并不会出现匹配。

譬如下图遍历到向右的 5 的时候，并不会跟前面的 -8 和 -5 发生匹配。

故整体的代码为：

向左数字的处理

向左数字的处理，相对来说就比较复杂了。 如果在遍历过程中遇到一个向左的数字，那么我们可以分为以下几种情况来讨论：

• 栈中没有元素
• 栈顶元素是向左的数字
• 栈顶元素是向右的数字

对于前两种情况而言，也是无需发生匹配的，我们直接令这个向左的数字入栈即可。 但对于第三种情况，是需要进行数字的匹配，那么这个时候就需要进行 栈顶向右数字的相关操作。

根据题意，这里可能会出现三种情况：

1. 向左数字的绝对值 abs(num) < 向右数字 stack[-1] 2. 向左数字的绝对值 abs(num) = 向右数字 stack[-1] 3. 向左数字的绝对值 abs(num) > 向右数字 stack[-1]

这里提到绝对值是因为向左数字在数值上必然是一个负数，使用绝对值来讨论是更加严谨的说明。

对于 情况1，向左的人会倒下体力修改为 0，而向右的人的体力会减去 abs(num)，故对应代码为：

对于 情况2，向左的人会倒下体力修改为 0，而向右的人也倒下可以直接令其出栈，故对应代码为：

对于 情况3，向左的人体力会减去 stack[-1]，而向右的人倒下可以直接令其出栈，故对应代码为：

到这里我们发现一个有意思的问题，如果是 情况3 出现，这个向左的人的体力并没有降为 0。 如果此时栈顶元素仍然是一个向右移动的人的话，仍然需要继续进行上述的判断。 因此，这里我们需要使用一个 while循环 来进行。

while 循环持续进行的条件有 3个：

• 栈不为空
• 栈顶元素向右
• 当前向左的人体力没有降到 0

即对应的代码为：

while 循环中，需要加上上述3个条件语句，来判断当前向左数字和栈顶向右数字的匹配情况。

而在 while 循环结束之后，num 仍然不一定降为 0。 举个例子，num 是一个向左移动且体力极其充沛的人（绝对值很大），大杀四方赢了所有栈顶元素中所有向右移动的人，那么 num 仍然不降为 0。 在这种情况下，我们必须在 while 外面再加一个判断，若 num 不为 0 则可以入栈。

将上述所有代码框架进行梳理，最终答案就呼之欲出了。

最后，大家可以思考一下最终答案栈中元素的构成会有什么样的特点。 A：栈中元素最终的构成，一定由两部分组成：【若干向左移动的人】 + 【若干向右移动的人】，这两部分的长度均可能为 0。

不同题目描述

特别注意，在部分考题中，遇到的设问是 输出最终逃生的人数。这非常容易修改代码。 在代码中只需要输出 len(stack) 而不是 stack 中的结果即可。

复杂度分析 设体力数组的长度为 n。这段代码虽然是 for 循环里套 while 循环，但时间复杂度并不是 O(n²)，而是均摊 O(n)。关键在于观察 while 循环体每执行一次会发生什么：要么栈顶那个向右的人被 pop 弹出（体力相等、或小于当前向左者这两个分支），要么把 num 置 0 直接终结本轮 while（向右者体力更大的分支）。每个数字整个过程中至多入栈一次、至多被弹出一次，所以所有 while 迭代的总次数被入栈总数 n 限制住，摊下来每个元素只被处理常数次。因此总时间复杂度 O(n)，瓶颈就是这一遍带栈的线性扫描。空间复杂度 O(n)：最坏情况没有任何相遇（例如所有人都向右移动），栈会保存全部 n 个数字；收尾把栈拼接成输出字符串同样是 O(n)。