Medium

题目描述

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

  1. 分配 一块大小为 size 的连续空闲内存单元并赋予 id mID 。
  2. 释放 给定 id mID 对应的所有内存单元。

注意：

  • 多个块可以被分配到同一个 mID 。
  • 你应该释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

实现 Allocator 类：

  • Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
  • int allocate(int size, int mID) 找到大小为 size 个连续空闲内存单元且位于最左侧的块，分配并赋予 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。
  • int freeMemory(int mID) 释放 id 为 mID 的所有内存单元。返回释放的内存单元数目。

示例 1：

输入
["Allocator", "allocate", "allocate", "allocate", "freeMemory", "allocate", "allocate", "allocate", "freeMemory", "allocate", "freeMemory"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
输出
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

解释
Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1,_,_,_,_,_,_,_,_,_] 。返回 0 。
loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2,_,_,_,_,_,_,_,_] 。返回 1 。
loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3,_,_,_,_,_,_,_] 。返回 2 。
loc.freeMemory(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1,_,3,_,_,_,_,_,_,_] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。
loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1,_,3,4,4,4,_,_,_,_] 。返回 3 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4,_,_,_,_] 。返回 1 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1,_,_,_] 。返回 6 。
loc.freeMemory(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [_,_,3,4,4,4,_,_,_,_] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找到 10 个连续的空闲内存单元，所以返回 -1 。
loc.freeMemory(7); // 释放 mID 为 7 的所有内存单元。内存数组保持不变，因为不存在 mID 为 7 的内存单元。返回 0 。

提示：

  • 1 <= n, size, mID <= 1000
  • allocate 和 freeMemory 最多被调用 1000 次

解题思路

这道题要求我们设计一个内存分配器，主要包含两个操作：分配连续内存块和释放指定 ID 的所有内存。

核心思路分析：

  1. 数据结构设计：使用一个数组来模拟内存，其中 0 表示空闲，非零值表示分配给某个 ID 的内存单元。

  2. 分配操作 (allocate)：

    • 从左到右扫描内存数组，寻找第一个长度为 size 的连续空闲块
    • 使用滑动窗口的思想，维护当前连续空闲块的长度
    • 找到合适的块后，将其标记为指定的 mID

  3. 释放操作 (freeMemory)：

    • 遍历整个内存数组，找到所有值为 mID 的内存单元
    • 将这些单元重置为 0（空闲状态）
    • 统计释放的内存单元数量

算法优化考虑：

  • 虽然可以考虑使用更复杂的数据结构（如线段树、区间树）来优化查找，但考虑到题目约束（n ≤ 1000），简单的数组模拟已经足够高效
  • 时间复杂度：allocate 为 O(n)，freeMemory 为 O(n)
  • 空间复杂度：O(n) 用于存储内存状态

这种直接模拟的方法思路清晰，实现简单，完全满足题目要求。

代码实现

class Allocator {
private:
    vector<int> memory;
    int n;
    
public:
    Allocator(int n) : n(n) {
        memory.resize(n, 0);
    }
    
    int allocate(int size, int mID) {
        int consecutiveFree = 0;
        
        for (int i = 0; i < n; i++) {
            if (memory[i] == 0) {
                consecutiveFree++;
                if (consecutiveFree == size) {
                    // 找到了合适的块，从 i - size + 1 开始分配
                    int start = i - size + 1;
                    for (int j = start; j <= i; j++) {
                        memory[j] = mID;
                    }
                    return start;
                }
            } else {
                consecutiveFree = 0;
            }
        }
        
        return -1;
    }
    
    int freeMemory(int mID) {
        int freedCount = 0;
        for (int i = 0; i < n; i++) {
            if (memory[i] == mID) {
                memory[i] = 0;
                freedCount++;
            }
        }
        return freedCount;
    }
};

class Allocator:

    def __init__(self, n: int):
        self.memory = [0] * n
        self.n = n

    def allocate(self, size: int, mID: int) -> int:
        consecutive_free = 0
        
        for i in range(self.n):
            if self.memory[i] == 0:
                consecutive_free += 1
                if consecutive_free == size:
                    # 找到了合适的块，从 i - size + 1 开始分配
                    start = i - size + 1
                    for j in range(start, i + 1):
                        self.memory[j] = mID
                    return start
            else:
                consecutive_free = 0
        
        return -1

    def freeMemory(self, mID: int) -> int:
        freed_count = 0
        for i in range(self.n):
            if self.memory[i] == mID:
                self.memory[i] = 0
                freed_count += 1
        return freed_count

public class Allocator {
    private int[] memory;
    private int n;
    
    public Allocator(int n) {
        this.n = n;
        this.memory = new int[n];
    }
    
    public int Allocate(int size, int mID) {
        int consecutiveFree = 0;
        
        for (int i = 0; i < n; i++) {
            if (memory[i] == 0) {
                consecutiveFree++;
                if (consecutiveFree == size) {
                    // 找到了合适的块，从 i - size + 1 开始分配
                    int start = i - size + 1;
                    for (int j = start; j <= i; j++) {
                        memory[j] = mID;
                    }
                    return start;
                }
            } else {
                consecutiveFree = 0;
            }
        }
        
        return -1;
    }
    
    public int FreeMemory(int mID) {
        int freedCount = 0;
        for (int i = 0; i < n; i++) {
            if (memory[i] == mID) {
                memory[i] = 0;
                freedCount++;
            }
        }
        return freedCount;
    }
}

var Allocator = function(n) {
    this.memory = new Array(n).fill(0);
    this.n = n;
};

Allocator.prototype.allocate = function(size, mID) {
    let consecutiveFree = 0;
    
    for (let i = 0; i < this.n; i++) {
        if (this.memory[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(n)O(n)
allocateO(n)O(1)
freeMemoryO(n)O(1)
总体空间复杂度-O(n)

说明：

  • 时间复杂度：所有操作都需要遍历内存数组，因此时间复杂度为 O(n)
  • 空间复杂度：需要 O(n) 的额外空间来存储内存状态数组
  • 在给定的约束条件下（n ≤ 1000，调用次数 ≤ 1000），这种解法完全满足性能要求