1860-增长的内存泄露

给你两个整数 memory1 和 memory2 分别表示两个内存条剩余可用内存的位数。现在有一个程序每秒递增的速度消耗着内存。

在第 i 秒（秒数从 1 开始），有 i 位内存被分配到 剩余内存较多
的内存条（如果两者一样多，则分配到第一个内存条）。如果两者剩余内存都不足 i 位，那么程序将 意外退出 。

请你返回一个数组，包含 __[crashTime, memory1crash, memory2crash] ，其中
crashTime是程序意外退出的时间（单位为秒）， __memory1crash __ 和 __memory2crash __
分别是两个内存条最后剩余内存的位数。

示例 1：

**输入：** memory1 = 2, memory2 = 2
**输出：** [3,1,0]
**解释：** 内存分配如下：
- 第 1 秒，内存条 1 被占用 1 位内存。内存条 1 现在有 1 位剩余可用内存。
- 第 2 秒，内存条 2 被占用 2 位内存。内存条 2 现在有 0 位剩余可用内存。
- 第 3 秒，程序意外退出，两个内存条分别有 1 位和 0 位剩余可用内存。

示例 2：

**输入：** memory1 = 8, memory2 = 11
**输出：** [6,0,4]
**解释：** 内存分配如下：
- 第 1 秒，内存条 2 被占用 1 位内存，内存条 2 现在有 10 位剩余可用内存。
- 第 2 秒，内存条 2 被占用 2 位内存，内存条 2 现在有 8 位剩余可用内存。
- 第 3 秒，内存条 1 被占用 3 位内存，内存条 1 现在有 5 位剩余可用内存。
- 第 4 秒，内存条 2 被占用 4 位内存，内存条 2 现在有 4 位剩余可用内存。
- 第 5 秒，内存条 1 被占用 5 位内存，内存条 1 现在有 0 位剩余可用内存。
- 第 6 秒，程序意外退出，两个内存条分别有 0 位和 4 位剩余可用内存。

提示：

• 0 <= memory1, memory2 <= 231 - 1

方法一：模拟

提示 1

模拟程序消耗内存的过程。

思路与算法

我们用 t 表示当前时刻，同时也是当前时刻程序会额外消耗内存的位数。为了模拟分配内存的过程，在 t 时刻，我们首先判断是否有内存条可以满足当前的额外内存需求。此时有两种情况：

• 如果不存在，那么程序将意外退出，同时按要求返回对应的值组成的数组；

• 如果存在，我们按照要求寻找剩余内存较多的内存条（相同时则选择内存条 1），并将对应的 memory}_1 或 memory}_2 减去 t。

代码

[sol1-C++]

class Solution {
public:
    vector<int> memLeak(int memory1, int memory2) {
        int t = 1;
        while (t <= max(memory1, memory2)){   // 是否可分配
            if (memory1 < memory2){   // 分配给 2
                memory2 -= t;
            }
            else {   // 分配给 1
                memory1 -= t;
            }
            ++t;
        }
        return {t, memory1, memory2};
    }
};

[sol1-Python3]

class Solution:
    def memLeak(self, memory1: int, memory2: int) -> List[int]:
        t = 1
        while t <= max(memory1, memory2):   # 是否可分配
            if memory1 < memory2:   # 分配给 2
                memory2 -= t
            else:   # 分配给 1
                memory1 -= t
            t += 1
        return [t, memory1, memory2]

复杂度分析

• 时间复杂度：O(\sqrt{\textit{memory}_1 + \textit{memory}_2})。

  假设 t 为意外退出的时刻，那么两个内存条一定可以容纳 t - 1 时刻及以前消耗的内存。因此我们有：

  \sum_{i = 1}^{t-1} i = t(t - 1)}{2} \le \textit{memory}_1 + \textit{memory}_2.

  亦即循环最多会进行 O(\sqrt{\textit{memory}_1 + \textit{memory}_2}) 次，而每次执行循环的时间复杂度为 O(1)。

• 空间复杂度：O(1)。