发表于 2025.02.25

• 不难想，但实现起来还是需要注意很多细节。首先，我们需要一个链表来记录未使用的区块，每次分配内存时，我们需要遍历链表找到一个合适的区块。其次，我们需要一个哈希表来记录已使用的区块，以便于释放内存时能够快速找到对应的区块。最后，我们在释放内存时，将归还的内存作为一个新的区块插入到链表中，然后需要注意合并左右相邻的区块。

  struct Node {
      Node* next;
      Node* prev;
  
      int size;
      int pos;
  
      Node(int pos, int size, Node* prev = nullptr, Node* next = nullptr) : pos(pos), size(size), prev(prev), next(next) {}
  };
  
  class Allocator {
  public:
      Allocator(int n) {
          head = new Node(0, n);
      }
  
      //// Helpers ////
      Node* make_dummy_head() {
          Node* dummy_head = new Node(-1, -1, nullptr, head);
          if (head) head->prev = dummy_head;
          return dummy_head;
      }
  
      void remove_dummy_head(Node* dummy_head) {
          head = dummy_head->next;
          if (head) head->prev = nullptr;
          delete dummy_head;
      }
  
      int allocate(int size, int mID) {
          auto* cur = head;
          while (cur && cur->size < size) cur = cur->next;
          if (!cur) return -1;
  
          // 找到一个空间合适的未使用区块
          int target_pos = cur->pos;
          allocated[mID].emplace_back(target_pos, size);
  
          Node* dummy_head = make_dummy_head();
  
          // 更新未使用区块信息
          if (cur->size == size) {  // 区块刚好合适
              // 从链表中移除掉
              if (cur->prev) cur->prev->next = cur->next;
              if (cur->next) cur->next->prev = cur->prev;
          } else {
              // 剥离掉一部分，更新该区块位置长度
              cur->pos += size;
              cur->size -= size;
          }
  
          remove_dummy_head(dummy_head);
  
          return target_pos;
      }
  
      int freeMemory(int mID) {
          if (!allocated.count(mID)) return 0;
          auto&& blocks = allocated[mID];
          // 按pos排序已使用的区块
          std::sort(blocks.begin(), blocks.end());
  
          Node* dummy_head = make_dummy_head();
  
          auto* cur = dummy_head;
          int free_unit_cnt = 0;
  
          // 逐个归还区块
          for (int i = 0; i < blocks.size(); ++i) {
              auto [pos, size] = blocks[i];
              free_unit_cnt += size;
              while (cur->next && cur->next->pos < pos) cur = cur->next;
              // 对于归还的内存，新建个区块
              auto* new_block = new Node(pos, size, cur, cur->next);
              if (new_block->prev) new_block->prev->next = new_block;
              if (new_block->next) new_block->next->prev = new_block;
              // 合并连续区块
              // 看左边
              if (new_block->prev && new_block->prev->pos + new_block->prev->size == pos) {
                  auto* merged = new_block->prev;  // 使用左侧区块作为合并结果
                  merged->size += size;
                  // 更新前后指向
                  merged->next = new_block->next;
                  if (merged->next) merged->next->prev = merged;
                  // 删除掉刚刚新建的区块，我们直接使用左边的区块就好了
                  delete new_block;
                  new_block = merged;
              }
              // 看右边
              if (new_block->next && new_block->pos + new_block->size == new_block->next->pos) {
                  auto* dropped = new_block->next;  // 遗弃掉右边的区块节点，使用新区快作为合并结果
                  new_block->size += dropped->size;
                  // 更新前后指向
                  new_block->next = dropped->next;
                  if (new_block->next) new_block->next->prev = new_block;
                  // 删除右边的区块节点
                  delete dropped;
              }
          }
  
          remove_dummy_head(dummy_head);
          
          blocks.clear();
          return free_unit_cnt;
      }
  private:
      // 使用链表记录未使用的区块
      Node* head;
      // 使用哈希表记录已使用的区块 mId -> 区块信息向量
      unordered_map<int, vector<pair<int, int>>> allocated;
  };

• LC 题目链接