895.最大频率栈.md

895.最大频率栈

/*
 * @lc app=leetcode.cn id=895 lang=typescript
 *
 * [895] 最大频率栈
 */

// @lc code=start

class FreqStack {
  constructor() {}

  push(val: number): void {}

  pop(): number {}
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * var obj = new FreqStack()
 * obj.push(val)
 * var param_2 = obj.pop()
 */
// @lc code=end

解法 1: 使用堆

class FreqStack {
  map = new Map<number, number[]>()
  id = 0
  // [num,cnt,index]
  heap = new Heap<[number, number, number]>((a, b) => {
    if (a[1] !== b[1]) {
      return b[1] - a[1]
    }
    return b[2] - a[2]
  })
  constructor() {}

  push(val: number): void {
    if (!this.map.has(val)) this.map.set(val, [])
    this.map.get(val).push(this.id)
    this.heap.push([val, this.map.get(val).length, this.id])
    this.id++
  }

  pop(): number {
    while (this.heap.size()) {
      const [v, c, i] = this.heap.pop()!
      const ids = this.map.get(v)
      if (ids.length !== c || ids[c - 1] !== i) continue
      ids.pop()
      if (ids.length) this.heap.push([v, c - 1, ids[c - 2]])
      return v
    }
    return -1
  }
}

class Heap<T = number> {
  private _heap: T[] = []
  constructor(...args: T extends number ? [((a: number, b: number) => number)?, T[]?] : [(a: T, b: T) => number, T[]?])
  constructor(private _comparator: (n1: T, n2: T) => number = ((a: number, b: number) => a - b) as any, arr?: T[]) {
    if (arr) {
      this._heap = [...arr]
      for (let i = arr.length >> 1; i; i--) this.down(i)
    }
  }
  private swap(i: number, j: number) {
    ;[this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]
  }
  private _has(i: number) {
    return Object.prototype.hasOwnProperty.call(this._heap, i)
  }
  private comparator(i: number, j: number) {
    return this._comparator(this._heap[i], this._heap[j]) < 0
  }
  private parent(i: number) {
    return (i - 1) >> 1
  }
  private children(i: number) {
    return [2 * i + 1, 2 * i + 2]
  }
  private up(i: number) {
    let parent = this.parent(i)
    while (i > 0 && this.comparator(i, parent)) {
      this.swap(i, parent)
      ;[i, parent] = [parent, (parent - 1) >> 1]
    }
  }
  private down(i: number) {
    let [left, right] = this.children(i)

    while (left < this._heap.length) {
      if (!this._has(right)) right = left
      if (this.comparator(right, left)) [left, right] = [right, left]
      if (this.comparator(i, left)) break

      this.swap(i, left)
      i = left
      ;[left, right] = [2 * i + 1, 2 * i + 2]
    }
  }
  push(node: T) {
    this._heap.push(node)
    this.up(this._heap.length - 1)
  }
  pop() {
    if (this.size() === 0) return null

    let res = this._heap[0]
    this.swap(0, this._heap.length - 1)
    this._heap.pop()
    this.down(0)
    return res
  }
  remove(i: number) {
    if (i >= this.size()) return

    let res = this._heap[i]
    this.swap(i, this._heap.length - 1)
    this._heap.pop()

    this.down(i)
    this.up(i)

    return res
  }
  modify(i: number, val: T) {
    if (i >= this.size()) return

    let res = this._heap[i]
    this._heap[i] = val

    this.down(i)
    this.up(i)
    return res
  }
  top() {
    if (this.size() === 0) return null

    return this._heap[0]
  }
  size() {
    return this._heap.length
  }
}

Case

test.each([
  {
    input: {
      ops: ['FreqStack', 'push', 'push', 'push', 'push', 'push', 'push', 'pop', 'pop', 'pop', 'pop'],
      params: [[], [5], [7], [5], [7], [4], [5], [], [], [], []],
    },
    output: [null, null, null, null, null, null, null, 5, 7, 5, 4],
  },
])('input: param = $input.param', ({ input: { ops, params }, output }) => {
  const cls = new FreqStack()
  const res = [null]
  for (let i = 1; i < ops.length; i++) {
    res.push(cls[ops[i]](...params[i]) ?? null)
  }
  expect(res).toEqual(output)
})