数据结构

LRU缓存

146.LRU缓存机制

我是链接

LRU 的全称是Least Recently Used，最近最少使用缓存淘汰策略。

// 实现双向链表节点类
class ListNode {
  constructor (key, value) {
    this.key = key
    this.value = value
    this.prev = null
    this.next = null
  }
}
class LRUCache {
  constructor (capacity) {
    this.capacity = capacity // 容量
    this.count = 0 // 已存储个数
    this.hash = {} // 记录 key => 节点 的映射
    this.dummyHead = new ListNode()
    this.dummyTail = new ListNode()
    this.dummyHead.next = this.dummyTail
    this.dummyTail.prev = this.dummyHead
  }
  // key 存在，将节点移到链表头部（删除当前节点 + 将节点添加到头部），否则，返回 -1
  get (key) {
    const node = this.hash[key]
    if (node) {
      this.removeFromList(node)
      this.addToHead(node)
      return node.value
    }
    return -1
  }
  // key存在，将value值替换，将节点移动到最前面。
  // key不存在：1.容量已满，删除尾节点，节点数减一，将新节点加入头部； 2.容量未满，将新节点加入头部，节点数加一
  put (key, value) {
    let node = this.hash[key]
    if (node) {
      node.value = value
      this.removeFromList(node)
      this.addToHead(node)
    } else {
      node = new ListNode(key, value)
      if (this.count === this.capacity) {
        const tail = this.dummyTail.prev
        delete this.hash[tail.key]
        this.count --
        this.removeFromList(tail)
      }
      this.addToHead(node)
      this.hash[key] = node
      this.count ++
    }
  }
  removeFromList (node) {
    node.prev.next = node.next
    node.next.prev = node.prev
  }
  // 添加节点至头部
  addToHead (node) {
    node.prev = this.dummyHead
    node.next = this.dummyHead.next
    this.dummyHead.next.prev = node
    this.dummyHead.next = node
  }
}

460. LFU 缓存

我是链接

维护 KV 表，KF 表，FK 表三个映射。

class LFUCache {
  constructor (capacity) {
    this.capacity = capacity
    this.KVMap = new Map() // key => value
    this.KFMap = new Map() // key => freq
    this.FKMap = new Map() // freq => Set(key1, key2)，这里用 Set 存储 key 可以方便增删去重
    this.minFreq = 0
  }
  addFreq (key) {
    // 获取现有次数 和 次数相应的 key 集合
    const freq = this.KFMap.get(key)
    const keySet = this.FKMap.get(freq)
    // 更新最小 freq
    if (this.minFreq === freq && keySet.size === 1) {
      this.minFreq += 1
    }
    // 当前次数集合去除原始key
    keySet.delete(key)
    // 更新 KF 和 FKSet
    this.KFMap.set(key, freq + 1)
    let newKeySet = this.FKMap.get(freq + 1)
    if (!newKeySet) {
      newKeySet = new Set()
      this.FKMap.set(freq + 1, newKeySet)
    }
    newKeySet.add(key)
  }
  get (key) {
    if (this.KVMap.has(key)) {
      // 增加次数
      this.addFreq(key)
      return this.KVMap.get(key)
    }
    return -1
  }
  put (key, value) {
    if (this.capacity === 0) return
    if (this.KVMap.has(key)) {
      this.KVMap.set(key, value)
      this.addFreq(key)
    } else {
      // 容量已满
      if (this.KVMap.size === this.capacity) {
        // 找到最小次数对应的最老 key
        const minKeySet = this.FKMap.get(this.minFreq) // Set{key1, key2}, 取出 key1
        const minKey = minKeySet.keys().next().value
        // 删除映射中的 key
        this.KVMap.delete(minKey)
        this.KFMap.delete(minKey)
        minKeySet.delete(minKey)
      }
      // 新增一个 key 及其映射
      this.KVMap.set(key, value)
      this.KFMap.set(key, 1)
      let oneSet = this.FKMap.get(1)
      if (!oneSet) {
        oneSet = new Set()
        this.FKMap.set(1, oneSet)
      }
      oneSet.add(key)
      this.minFreq = 1
    }
  }
}

单调栈

// 模板
let res = [] // 存放答案
let stack = []
for (let i = n - 1; i >= 0; i --) {
  let top = stack[stack.length - 1]
  while (stack.length && top <= nums[i]) {
    stack.pop()
  }
  let restTop = stack[stack.length - 1]
  res[i] = stack.length ? restTop : -1
  stack.push(nums[i])
}

739.每日温度

我是链接

var dailyTemperatures = function(temperatures) {
  let res = []
  let deque = []
  for (let i = temperatures.length - 1; i >= 0; i --) {
    while (deque.length && temperatures[deque[deque.length - 1]] <= temperatures[i]) {
      deque.pop()
    }
    res[i] = deque.length ? deque[deque.length - 1] - i : 0
    deque.push(i)
  }
  return res
};

496.下一个更大的元素I

我是链接

var nextGreaterElement = function(nums1, nums2) {
  const n = nums2.length
  let s = []
  let hash = {} //存放答案，作为 nums1 的映射
  let res = []
  for (let i = n - 1; i >= 0; i --) {
    while (s.length && s[s.length - 1] <= nums2[i]) {
      s.pop()
    }
    hash[nums2[i]] = s.length ? s[s.length - 1] : -1
    s.push(nums2[i])
  }
  for (let i = 0; i < nums1.length; i ++) {
    res[i] = hash[nums1[i]] || -1
  }
  return res
};

503.下一个更大的元素II

我是链接

// 这里数组是环形的，可以将原数组接在最后一个元素后面
var nextGreaterElements = function(nums) {
  let arr = [...nums, ...nums]
  const n = arr.length
  let res = []
  let s = []
  for (let i = n - 1; i >= 0; i --) {
    while (s.length && s[s.length - 1] <= arr[i]) {
      s.pop()
    }
    res[i] = s.length ? s[s.length - 1] : -1
    s.push(arr[i])
  }
  return res.slice(0, n / 2)
};

处理环形数组 🌟🌟

对索引进行求模，模拟长度加长的情况

// let arr = [1, 2, 3]
// const n = arr.length
// for (let i = 2 * n - 1; i >= 0; i --) {
//     console.log(i%n, arr[i%n])
// }
var nextGreaterElements = function(nums) {
  const n = nums.length
  let res = []
  let s = []
  for (let i = 2 * n - 1; i >= 0; i --) {
    while (s.length && s[s.length - 1] <= nums[i % n]) {
      s.pop()
    }
    res[i % n] = s.length ? s[s.length - 1] : -1
    s.push(nums[i % n])
  }
  return res
};

单调队列

239.滑动窗口最大的值

我是链接

var maxSlidingWindow = function(nums, k) {
  const n = nums.length
  let dequeue = []
  let res = []
  for (let i = 0; i < n; i ++) {
    // 合法性检测,超出 k个 窗口删除
    if (i - dequeue[0] >= k) {
      dequeue.shift()
    }
    while (dequeue.length && nums[dequeue[dequeue.length - 1]] <= nums[i]) {
      dequeue.pop()
    }
    dequeue.push(i)
    // k 为 3， 区间[0-2]开始算最大值
    if (i >= k -1) {
      res.push(nums[dequeue[0]])
    }
  }
  return res
};

最小栈

155. 最小栈

我是链接

// 思路: 用两个栈，一个min栈用来存每次新增时当前栈最小值
class MinStack {
  constructor () {
    this.stack = []
    this.minStack = []
  }
  top () {
    return this.stack[this.stack.length - 1]
  }
  push (x) {
    this.stack.push(x)
    const min = Math.min(...this.stack)
    this.minStack.push(min)
  }
  pop () {
    this.stack.pop()
    this.minStack.pop()
  }
  getMin () {
    return this.minStack[this.minStack.length - 1]
  }
}