P5100. 空栈压数

解题思路

注意，本题最初见于 华为2023年校招暑期实习 的题目，在 OJ 上直接搜索 空栈压数 即可搜索得到题目。

由于本题的数据量较小，最多仅为 1000。可以直接使用 栈 的数据结构，对题目进行 模拟 即可。

出栈情况的归纳

题目所给定的两种出栈情况，实际上可以归纳为 同一种表述。 当某一个元素即将入栈时，如果发现栈顶的若干连续元素的和恰好等于该元素，则令栈中的这些若干连续元素出栈，换成将 两倍 的该元素入栈。

所以我们只需要在每一个元素入栈之前，都进行上述过程的判断即可。

核心函数设计

我们可以构建这样的一个函数：

在这个函数中，我们构建了参数 top_sum 表示栈顶元素和的情况，用索引 idx 从后往前逐个遍历。 一旦发现 top_sum >= num 的时候，则退出 while 循环。

退出 while 的时候，我们还需进一步做出判断，若：

• `top_sum == num`，说明此时是需要 弹出若干连续栈顶元素 的，并且需要令 两倍的 `num` 入栈
• `top_sum != num`，说明此时是 无需弹出 若干连续栈顶元素的，把 num 入栈

重复判断的处理

特别需要注意的地方在于，如果此时我们是要把两倍的 num 入栈，那么这个时候又是一个新的数 2 * num 入栈，我们需要 重复判断 是否存在若干连续栈顶元素的和为当前入栈的 2 * num 这个过程。

比如题目描述中所给的例子，入栈顺序是 6 1 2 3 时，当 3 准备入栈时，发现栈顶元素 2 1 的和为 3，此时会弹出 2 1，将 3 * 2 = 6 作为即将入栈的元素。而当 6 准备入栈时，又发现了此时栈顶元素 6 和准备入栈的 6 相等，因此将栈顶元素 6 弹出，令 6 * 2 = 12 入栈。

由于无法判断上述重复判断入栈的过程需要几次，因此我们在函数外部设置了一个 `while` 循环。 使用一个 bool 类型标志 flag_continue_loop 来表示，在 check_stack_top(stack, num) 函数中我们是否弹出了若干连续栈顶元素并且令 2 * num 准备入栈。

相对应的，check_stack_top(stack, num) 函数也需要加上关于 flag_continue_loop 的修改。 我们可以把 flag_continue_loop 作为一个 全局变量 来使用，当：

• 分支进入 top_sum == num 的时候，修改 flag_continue_loop = True
• 分支进入 top_sum != num 的时候，修改 flag_continue_loop = False

最终 check_stack_top(stack, num) 呈现的代码为：

将上述所有代码组织到一起，加上输入和输出内容，本题就完成了。

复杂度分析

设 n 为输入数字的个数。

• 时间复杂度：最坏 O(n^2)。外层 for 循环逐个处理 n 个待入栈数字；每次调用 check_stack_top 都要用 top_sum 从栈顶往下逐个累加，直到和不小于 num 或扫完整个栈，单次最坏是 O(n)。压缩合并可能连锁发生（合并出的 2*num 又触发新一轮判断），但每次成功合并至少弹出 2 个元素、只压回 1 个，栈的规模净减少至少 1，因此整个过程中合并的总次数不超过 n 次；check_stack_top 的调用总数是 O(n) 级别，每次 O(n)，合计 O(n^2)。Python 版中 stack[:idx+1] 的切片复制单次也是 O(n)，不改变总量级。按现有解析中「数据量最多 1000」的规模，O(n^2) 在时限内绰绰有余。
• 空间复杂度：O(n)。栈中最多同时存放 n 个元素；其余只有 top_sum、idx、flag_continue_loop 等常数个辅助变量（切片产生的新栈与原栈同量级，仍为 O(n)）。