/*
* @lc app=leetcode.cn id=2034 lang=typescript
*
* [2034] 股票价格波动
*/
// @lc code=start
class StockPrice {
constructor() {}
update(timestamp: number, price: number): void {}
current(): number {}
maximum(): number {}
minimum(): number {}
}
/**
* Your StockPrice object will be instantiated and called as such:
* var obj = new StockPrice()
* obj.update(timestamp,price)
* var param_2 = obj.current()
* var param_3 = obj.maximum()
* var param_4 = obj.minimum()
*/
// @lc code=end
使用一个哈希表来存储所有时间对应的股票价格,保存当前的最晚时间,使用一个小顶堆和大顶堆来存储股票价格,方便去最大和最小值.
在取最大或最小值时,先判断当前取出的价格是否为最新价格,跟哈希表中对应时间的价格对比即可,如果不一样,则为过期价格,舍弃该价格取下一个.
class StockPrice {
private timeMap = new Map<number, number>()
private minHeap = new Heap<[number, number]>((a, b) => a[1] <= b[1])
private maxHeap = new Heap<[number, number]>((a, b) => a[1] >= b[1])
private last = -Infinity
constructor() {}
update(timestamp: number, price: number): void {
this.timeMap.set(timestamp, price)
this.minHeap.push([timestamp, price])
this.maxHeap.push([timestamp, price])
this.last = Math.max(this.last, timestamp)
}
current(): number {
return this.timeMap.get(this.last)!
}
maximum(): number {
const { timeMap, maxHeap } = this
let cur = maxHeap.top()!
while (timeMap.get(cur[0]) !== cur[1]) {
maxHeap.pop()
cur = maxHeap.top()!
}
return cur[1]
}
minimum(): number {
const { timeMap, minHeap } = this
let cur = minHeap.top()!
while (timeMap.get(cur[0]) !== cur[1]) {
minHeap.pop()
cur = minHeap.top()!
}
return cur[1]
}
}
class Heap<T> {
private _heap: T[] = []
constructor(private _comparator: (n1: T, n2: T) => boolean) {}
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])
}
push(node: T) {
this._heap.push(node)
let cur = this._heap.length - 1
let parent = (cur - 1) >> 1
while (cur > 0 && this.comparator(cur, parent)) {
this.swap(cur, parent)
;[cur, parent] = [parent, (parent - 1) >> 1]
}
}
pop() {
if (this.size() === 0) return null
let res = this._heap[0]
this.swap(0, this._heap.length - 1)
this._heap.pop()
let cur = 0,
left = 2 * cur + 1,
right = 2 * cur + 2
while (left < this._heap.length) {
if (!this._has(right)) right = left
if (this.comparator(right, left)) [left, right] = [right, left]
if (this.comparator(cur, left)) break
this.swap(cur, left)
cur = left
;[left, right] = [2 * cur + 1, 2 * cur + 2]
}
return res
}
top() {
if (this.size() === 0) return null
return this._heap[0]
}
size() {
return this._heap.length
}
}
test.each([
{
input: {
op: ['StockPrice', 'update', 'update', 'current', 'maximum', 'update', 'maximum', 'update', 'minimum'],
params: [[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []],
},
output: [null, null, null, 5, 10, null, 5, null, 2],
},
])('input: param = $input.param', ({ input: { op, params }, output }) => {
let res: (null | number)[] = [null]
const stockPrice = new StockPrice()
for (let i = 1; i < params.length; i++) {
const param = params[i]
if (op[i] === 'update') {
stockPrice.update(param[0], param[1])
res.push(null)
} else {
res.push(stockPrice[op[i] as 'current' | 'maximum' | 'minimum']())
}
}
expect(res).toEqual(output)
})