Medium

题目描述

给你两个整数 memory1 和 memory2 分别表示两个内存条上的可用内存（以位为单位）。现在有一个有缺陷的程序正在运行，它每秒钟都会消耗递增的内存量。

在第 i 秒（从 1 开始），程序会从可用内存更多的内存条中分配 i 位内存（如果两个内存条的可用内存相同，则从第一个内存条分配）。如果两个内存条都没有至少 i 位的可用内存，程序就会崩溃。

返回一个包含 [crashTime, memory1crash, memory2crash] 的数组，其中 crashTime 是程序崩溃的时间（以秒为单位），memory1crash 和 memory2crash 分别是第一个和第二个内存条的剩余可用内存位数。

示例 1：

输入：memory1 = 2, memory2 = 2
输出：[3,1,0]
解释：内存分配如下：
- 第 1 秒，从内存条 1 分配 1 位内存。第一个内存条现在有 1 位可用内存。
- 第 2 秒，从内存条 2 分配 2 位内存。第二个内存条现在有 0 位可用内存。
- 第 3 秒，程序崩溃。内存条分别有 1 和 0 位可用内存。

示例 2：

输入：memory1 = 8, memory2 = 11
输出：[6,0,4]
解释：内存分配如下：
- 第 1 秒，从内存条 2 分配 1 位内存。第二个内存条现在有 10 位可用内存。
- 第 2 秒，从内存条 2 分配 2 位内存。第二个内存条现在有 8 位可用内存。
- 第 3 秒，从内存条 1 分配 3 位内存。第一个内存条现在有 5 位可用内存。
- 第 4 秒，从内存条 2 分配 4 位内存。第二个内存条现在有 4 位可用内存。
- 第 5 秒，从内存条 1 分配 5 位内存。第一个内存条现在有 0 位可用内存。
- 第 6 秒，程序崩溃。内存条分别有 0 和 4 位可用内存。

约束条件：

  • 0 <= memory1, memory2 <= 2³¹ - 1

解题思路

这道题要求模拟内存分配的过程，直到程序崩溃。

核心思路：

  1. 每秒分配的内存量递增（第i秒分配i位内存）
  2. 总是从内存更多的内存条分配，相同时优先选择第一个内存条
  3. 当两个内存条都无法满足当前秒数的内存需求时，程序崩溃

直接模拟解法： 最直观的方法是逐秒模拟分配过程。每一秒：

  • 判断哪个内存条有更多可用内存
  • 从该内存条分配当前秒数对应的内存量
  • 检查是否还能继续分配

这种方法简单易懂，但时间复杂度较高，在内存量很大时可能超时。

优化的数学解法： 可以通过数学方法快速跳过连续分配给同一个内存条的时间段，直接计算能分配多少秒，然后更新内存状态。这样可以大幅减少循环次数。

考虑到约束条件和实际测试情况，直接模拟解法在大多数情况下都能通过，代码更简洁易懂，因此推荐使用模拟解法。

代码实现

class Solution {
public:
    vector<int> memLeak(int memory1, int memory2) {
        int time = 1;
        
        while (max(memory1, memory2) >= time) {
            if (memory1 >= memory2) {
                memory1 -= time;
            } else {
                memory2 -= time;
            }
            time++;
        }
        
        return {time, memory1, memory2};
    }
};

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

public class Solution {
    public int[] MemLeak(int memory1, int memory2) {
        int time = 1;
        
        while (Math.Max(memory1, memory2) >= time) {
            if (memory1 >= memory2) {
                memory1 -= time;
            } else {
                memory2 -= time;
            }
            time++;
        }
        
        return new int[] {time, memory1, memory2};
    }
}

/**
 * @param {number} memory1
 * @param {number} memory2
 * @return {number[]}
 */
var memLeak = function(memory1, memory2) {
    let time = 1;
    
    while (Math.max(memory1, memory2) >= time) {
        if (memory1 >= memory2) {
            memory1 -= time;
        } else {
            memory2 -= time;
        }
        time++;
    }
    
    return [time, memory1, memory2];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(√(memory1 + memory2))，程序大约在第 √(memory1 + memory2) 秒崩溃
空间复杂度O(1)，只使用常数额外空间