What is the main pattern in Incremental Memory Leak?

The core pattern is Math plus Simulation. You simulate the allocation exactly as written, then use the triangular sum 1 + 2 + ... + t to explain why the number of steps is only about the square root of the total memory.

Why is the upper bound for the number of seconds small?

After t successful allocations, the program has used t(t + 1)/2 bits total. Since that total cannot exceed memory1 + memory2 before the crash, t is bounded by a square-root relationship, which keeps the simulation short.

Why does the equal-memory rule matter so much?

Because the next subtraction can change which stick becomes smaller later, the tie rule affects the whole future path. In this problem, equal memory must allocate to stick 1, and ignoring that detail produces the wrong crash state.

Can I solve LeetCode 1860 without simulation?

You can derive parts of the behavior with math, especially the upper bound, but a fully math-only implementation is usually less readable than the direct simulation. For interview code, the clean simulation plus a short proof is the safer choice.

What should I return when the program crashes?

Return the current second as crashTime, along with the remaining memory on stick 1 and stick 2 before any failed allocation is applied. The failed request is not subtracted from either stick.

#1860

Medium

auto_awesome数学·结合·模拟

LeetCode 题解工作台

增长的内存泄露

给你两个整数 memory1 和 memory2 分别表示两个内存条剩余可用内存的位数。现在有一个程序每秒递增的速度消耗着内存。在第 i 秒（秒数从 1 开始），有 i 位内存被分配到剩余内存较多的内存条（如果两者一样多，则分配到第一个内存条）。如果两者剩余内存都不足 i 位，那么程序将意外…

数学模拟

题目描述

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

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

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

示例 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 <= 2³¹ - 1

lightbulb

解题思路

方法一：模拟

我们直接模拟内存的分配。

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

\sum_{i=1}^{t-1} i = \frac{t\times (t-1)}{2} \leq (m_1+m_2)

时间复杂度 $O(\sqrt{m_1+m_2})$ ，其中 $m_1$ , $m_2$ 分别为两个内存条的内存大小。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def memLeak(self, memory1: int, memory2: int) -> List[int]:
        i = 1
        while i <= max(memory1, memory2):
            if memory1 >= memory2:
                memory1 -= i
            else:
                memory2 -= i
            i += 1
        return [i, memory1, memory2]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
You notice that the tie rule is not cosmetic: sending equal-memory cases to stick 1 changes the final crash state.
question_mark
You justify the loop bound with triangular numbers instead of hand-waving that simulation is probably fine.
question_mark
You keep the implementation state minimal: current second, memory1, and memory2 are enough.

warning

常见陷阱

外企场景

error
Allocating to stick 2 on ties, which breaks the sample with memory1 = 2 and memory2 = 2.
error
Stopping when the larger stick cannot fit the next request, even though the smaller stick might still be able to fit it.
error
Overengineering the solution and missing the real interview question, which is the crash-time bound from increasing requests.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the tie rule to prefer stick 2, which forces different crash states even when the high-level simulation stays the same.
arrow_right_alt
Add three or more memory sticks, where each second goes to the stick with the most available memory.
arrow_right_alt
Ask for the full allocation history instead of only [crashTime, memory1crash, memory2crash].

help

常见问题

外企场景

继续练习

#1823 找出游戏的获胜者 #1806 还原排列的最少操作步数 #2028 找出缺失的观测数据