输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

// 查找和修改需要O(1)的时间复杂度，所以可以用哈希表进行存储
// 关键在于怎么去维护各关键字最近使用的情况
// 各关键字需要按照使用时间(get和put都会更新)进行排序，才能在删除时直接删除最旧关键字从而达到O(1)时间复杂度
// 我们可以用一个双向链表（因为双向链表可以快速实现自删）来维护关键字的使用时间
// 并且我们将每个关键字的节点存储到哈希表，这样就可以快速找到对应的节点，然后放到头节点。
// 我们同时维护一个尾节点，删除时只需要删除最后一个节点即可
class LRUListNode {
  public key: number;
  public val: number;
  public next: LRUListNode | null;
  public prev: LRUListNode | null;

  constructor(key?: number, val?: number, next?: LRUListNode | null, prev?: LRUListNode | null) {
    this.key = key ?? -1;
    this.val = val ?? -1;
    this.next = next ?? null;
    this.prev = prev ?? null;
  }
}

class LRUCache {
  private capacity: number;
  private map: Map<number, LRUListNode>;
  private dummyHead: LRUListNode; // 虚拟头节点（哨兵）
  private dummyTail: LRUListNode; // 虚拟尾节点（哨兵）

  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map<number, LRUListNode>();
    
    // 初始化双向链表：虚拟头和虚拟尾互相指向
    this.dummyHead = new LRUListNode();
    this.dummyTail = new LRUListNode();
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }

  // 辅助方法：将节点移动到链表头部（虚拟头之后）
  private moveToHead(node: LRUListNode): void {
    // 1. 先从原位置移除节点
    this.removeNode(node);
    // 2. 插入到虚拟头之后
    this.addToHead(node);
  }

  // 辅助方法：添加节点到链表头部
  private addToHead(node: LRUListNode): void {
    node.prev = this.dummyHead;
    node.next = this.dummyHead.next;
    this.dummyHead.next.prev = node;
    this.dummyHead.next = node;
  }

  // 辅助方法：删除链表中的指定节点
  private removeNode(node: LRUListNode): void {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  // 辅助方法：删除链表尾节点（最久未使用的节点）
  private removeTail(): LRUListNode {
    const tailNode = this.dummyTail.prev; // 真实尾节点是虚拟尾的prev
    this.removeNode(tailNode);
    return tailNode;
  }

  // 查找key对应的value，不存在返回-1，存在则移到头部
  public get(key: number): number {
    if (!this.map.has(key)) {
      return -1;
    }
    const node = this.map.get(key)!; // 非空断言（已判断存在）
    this.moveToHead(node);
    return node.val;
  }

  // 添加/更新key-value，超出容量则删除最久未使用的节点
  public put(key: number, value: number): void {
    if (this.map.has(key)) {
      // 存在该key：更新值并移到头部
      const node = this.map.get(key)!;
      node.val = value;
      this.moveToHead(node);
    } else {
      // 不存在该key：新建节点
      const newNode = new LRUListNode(key, value);
      this.map.set(key, newNode);
      this.addToHead(newNode);

      // 超出容量：删除尾节点
      if (this.map.size > this.capacity) {
        const tailNode = this.removeTail();
        this.map.delete(tailNode.key);
      }
    }
  }
}



/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */