设计内存分配器

You are given an integer n representing the size of a 0-indexed memory array. All memory units are initially free.

You have a memory allocator with the following functionalities:

1. Allocate a block of size consecutive free memory units and assign it the id mID.
2. Free all memory units with the given id mID.

Note that:

• Multiple blocks can be allocated to the same mID.
• You should free all the memory units with mID, even if they were allocated in different blocks.

Implement the Allocator class:

• Allocator(int n) Initializes an Allocator object with a memory array of size n.
• int allocate(int size, int mID) Find the leftmost block of size consecutive free memory units and allocate it with the id mID. Return the block's first index. If such a block does not exist, return -1.
• int free(int mID) Free all memory units with the id mID. Return the number of memory units you have freed.

 

Example 1:

Input
["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
Output
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

Explanation
Allocator loc = new Allocator(10); // Initialize a memory array of size 10. All memory units are initially free.
loc.allocate(1, 1); // The leftmost block's first index is 0. The memory array becomes [1,_,_,_,_,_,_,_,_,_]. We return 0.
loc.allocate(1, 2); // The leftmost block's first index is 1. The memory array becomes [1,2,_,_,_,_,_,_,_,_]. We return 1.
loc.allocate(1, 3); // The leftmost block's first index is 2. The memory array becomes [1,2,3,_,_,_,_,_,_,_]. We return 2.
loc.free(2); // Free all memory units with mID 2. The memory array becomes [1,_, 3,_,_,_,_,_,_,_]. We return 1 since there is only 1 unit with mID 2.
loc.allocate(3, 4); // The leftmost block's first index is 3. The memory array becomes [1,_,3,4,4,4,_,_,_,_]. We return 3.
loc.allocate(1, 1); // The leftmost block's first index is 1. The memory array becomes [1,1,3,4,4,4,_,_,_,_]. We return 1.
loc.allocate(1, 1); // The leftmost block's first index is 6. The memory array becomes [1,1,3,4,4,4,1,_,_,_]. We return 6.
loc.free(1); // Free all memory units with mID 1. The memory array becomes [_,_,3,4,4,4,_,_,_,_]. We return 3 since there are 3 units with mID 1.
loc.allocate(10, 2); // We can not find any free block with 10 consecutive free memory units, so we return -1.
loc.free(7); // Free all memory units with mID 7. The memory array remains the same since there is no memory unit with mID 7. We return 0.

 

Constraints:

• 1 <= n, size, mID <= 1000
• At most 1000 calls will be made to allocate and free.

/*
 * 思路：
 * 使用Java Stream实现内存分配器。我们将使用IntStream来遍历内存数组。
 * allocate操作中使用IntStream找到第一个符合要求的空闲块，并分配给mID。
 * free操作中使用IntStream释放所有mID对应的内存单元。
 */

import java.util.stream.IntStream;

public class AllocatorStream {
    private int[] memory;

    public AllocatorStream(int n) {
        memory = new int[n];
    }

    public int allocate(int size, int mID) {
        int start = IntStream.range(0, memory.length - size + 1)
            .filter(i -> IntStream.range(i, i + size).allMatch(j -> memory[j] == 0))
            .findFirst()
            .orElse(-1);
        if (start != -1) {
            IntStream.range(start, start + size).forEach(i -> memory[i] = mID);
        }
        return start;
    }

    public int free(int mID) {
        int freed = (int) IntStream.range(0, memory.length)
            .filter(i -> memory[i] == mID)
            .peek(i -> memory[i] = 0)
            .count();
        return freed;
    }
}

该题解采用了一个列表 space 来维护内存分配的状态。每个元素是一个三元组 [ID, cnt, idx]，表示从下标 idx 开始，有 cnt 个连续的内存单元被分配给了 ID。如果 ID 为 -1，则表示这些内存单元是空闲的。在分配内存时，遍历 space，找到第一个空闲且大小足够的块，然后更新这个块的状态，并在需要时插入一个新的空闲块。在释放内存时，将所有属于给定 mID 的块标记为空闲，并合并连续的空闲块。

O(n)

O(n)