2034.股票价格波动

链接：2034.股票价格波动
难度：Medium
标签：设计、哈希表、数据流、有序集合、堆（优先队列）
简介：请你设计一个算法，实现：更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将   更正   之前的错误价格。找到当前记录里 最新股票价格  。最新股票价格   定义为时间戳最晚的股票价格。找到当前记录里股票的 最高价格  。找到当前记录里股票的 最低价格  。

题解 1 - typescript

• 编辑时间：2022-01-23
• 执行用时：692ms
• 内存消耗：79.2MB
• 编程语言：typescript
• 解法介绍：维护堆内下标。

class Node {
  constructor(
    public timestamp: number,
    public price: number,
    public imax: number,
    public imin: number
  ) {}
}
class Heap<Node> {
  private arr: Node[] = [];
  get isEmpty() {
    return this.size === 0;
  }
  get size() {
    return this.arr.length;
  }
  get top() {
    return this.arr[0];
  }
  constructor(private compare: (t1: Node, t2: Node) => number, private idx_field: string) {}
  add(num: Node): void {
    this.arr.push(num);
    this.shiftUp(this.size - 1);
  }
  remove(): Node {
    const num = this.arr.shift()!;
    if (this.size) {
      this.arr.unshift(this.arr.pop()!);
      this.shiftDown(0);
    }
    return num;
  }
  shiftUp(index: number): void {
    if (index === 0) return;
    const parentIndex = (index - 1) >> 1;
    if (this.compare(this.arr[index], this.arr[parentIndex]) > 0) {
      this.arr[index][this.idx_field] = parentIndex;
      this.arr[parentIndex][this.idx_field] = index;
      [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]];
      this.shiftUp(parentIndex);
    }
  }
  shiftDown(index: number): void {
    let childrenIndex = index * 2 + 1;
    if (childrenIndex > this.size - 1) return;
    if (
      childrenIndex + 1 <= this.size - 1 &&
      this.compare(this.arr[childrenIndex + 1], this.arr[childrenIndex]) > 0
    ) {
      childrenIndex++;
    }
    if (this.compare(this.arr[childrenIndex], this.arr[index]) > 0) {
      this.arr[index][this.idx_field] = childrenIndex;
      this.arr[childrenIndex][this.idx_field] = index;
      [this.arr[childrenIndex], this.arr[index]] = [this.arr[index], this.arr[childrenIndex]];
      this.shiftDown(childrenIndex);
    }
  }
  *[Symbol.iterator](): IterableIterator<Node> {
    for (const t of this.arr) {
      yield t;
    }
  }
}
class StockPrice {
  heap_max = new Heap<Node>((t1, t2) => t1.price - t2.price, 'imax');
  heap_min = new Heap<Node>((t1, t2) => t2.price - t1.price, 'imin');
  map = new Map<number, Node>();
  time_max = -1;
  update(timestamp: number, price: number): void {
    this.time_max = Math.max(this.time_max, timestamp);
    const cnt = this.map.size;
    let node = this.map.get(timestamp);
    if (node) {
      node.price = price;
      this.heap_max.shiftUp(node.imax);
      this.heap_max.shiftDown(node.imax);
      this.heap_min.shiftUp(node.imin);
      this.heap_min.shiftDown(node.imin);
    } else {
      this.map.set(timestamp, (node = new Node(timestamp, price, cnt, cnt)));
      this.heap_max.add(node);
      this.heap_min.add(node);
    }
  }
  current(): number {
    return this.map.get(this.time_max)!.price;
  }
  maximum(): number {
    return this.heap_max.top.price;
  }
  minimum(): number {
    return this.heap_min.top.price;
  }
}

题解 2 - python

• 编辑时间：2023-10-08
• 执行用时：1140ms
• 内存消耗：57.04MB
• 编程语言：python
• 解法介绍：有序集合。

from sortedcontainers import SortedDict
class StockPrice:
    def __init__(self):
        self.cur_time = -1
        self.cur_price = 0
        self.time_map = SortedDict()
        self.max_map = SortedDict()
        self.min_map = SortedDict()
    def update_map(self, map, key, d):
        if key not in map: map[key] = 0
        map[key] += d
        if map[key] == 0: del map[key]
    def update(self, timestamp: int, price: int) -> None:
        if timestamp in self.time_map: 
            cur_price = self.time_map[timestamp]
            self.update_map(self.max_map, cur_price, -1)
            self.update_map(self.min_map, cur_price, -1)
        self.update_map(self.max_map, price, 1)
        self.update_map(self.min_map, price, 1)
        self.time_map[timestamp] = price
        if self.cur_time <= timestamp:
            self.cur_time = timestamp
            self.cur_price = price
    def current(self) -> int:
        return self.cur_price
    def maximum(self) -> int:
        return self.max_map.keys()[-1]
    def minimum(self) -> int:
        return self.min_map.keys()[0]