跳转至

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

解法

方法一：模拟

思考

第 \(i\) 秒消耗 \(i\) 单位内存，优先从当前较大的一根扣除，直到两根都不够。内存可达 \(2^{31}-1\)，但消耗是平方增长，秒数约为 \(\sqrt{m_1+m_2}\)，直接模拟即可。

从 \(i=1\) 开始，比较两根剩余量，够则减去 \(i\) 并递增，否则返回当前秒与剩余。

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

假设 \(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
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int[] memLeak(int memory1, int memory2) {
        int i = 1;
        for (; i <= Math.max(memory1, memory2); ++i) {
            if (memory1 >= memory2) {
                memory1 -= i;
            } else {
                memory2 -= i;
            }
        }
        return new int[] {i, memory1, memory2};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> memLeak(int memory1, int memory2) {
        int i = 1;
        for (; i <= max(memory1, memory2); ++i) {
            if (memory1 >= memory2) {
                memory1 -= i;
            } else {
                memory2 -= i;
            }
        }
        return {i, memory1, memory2};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func memLeak(memory1 int, memory2 int) []int {
    i := 1
    for ; i <= memory1 || i <= memory2; i++ {
        if memory1 >= memory2 {
            memory1 -= i
        } else {
            memory2 -= i
        }
    }
    return []int{i, memory1, memory2}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function memLeak(memory1: number, memory2: number): number[] {
    let i = 1;
    for (; i <= Math.max(memory1, memory2); ++i) {
        if (memory1 >= memory2) {
            memory1 -= i;
        } else {
            memory2 -= i;
        }
    }
    return [i, memory1, memory2];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {number} memory1
 * @param {number} memory2
 * @return {number[]}
 */
var memLeak = function (memory1, memory2) {
    let i = 1;
    for (; i <= Math.max(memory1, memory2); ++i) {
        if (memory1 >= memory2) {
            memory1 -= i;
        } else {
            memory2 -= i;
        }
    }
    return [i, memory1, memory2];
};

评论