1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| class PriorityQueue1<T> {
arr: T[];
compare: (a: T, b: T) => number;
constructor(props: { compare: (a: T, b: T) => number }) {
const { compare } = props;
this.compare = compare;
this.arr = [];
}
swap(arr, index1, index2) {
const temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
enqueue(a) {
this.arr.push(a);
this.bubbleUp(this.arr.length - 1);
}
dequeue() {
this.delete(0);
}
bubbleUp(index) {
if (this.arr.length <= 1 || index <= 0) {
return;
}
const pre = Math.floor((index - 1) / 2);
if (this.compare(this.arr[index], this.arr[pre]) > 0) {
this.swap(this.arr, pre, index);
this.bubbleUp(pre);
}
}
delete(index) {
this.swap(this.arr, index, this.arr.length - 1);
this.arr.pop();
this.sinkDown(index);
}
sinkDown(index) {
if (this.arr.length <= 1 || index >= this.arr.length - 1) {
return;
}
if (
(index * 2 + 1 < this.arr.length &&
this.compare(this.arr[index], this.arr[index * 2 + 1]) < 0) ||
(index * 2 + 2 < this.arr.length &&
this.compare(this.arr[index], this.arr[index * 2 + 2]) < 0)
) {
if (
index * 2 + 2 >= this.arr.length ||
this.compare(this.arr[index * 2 + 1], this.arr[index * 2 + 2]) > 0
) {
this.swap(this.arr, index, index * 2 + 1);
this.sinkDown(index * 2 + 1);
} else {
this.swap(this.arr, index, index * 2 + 2);
this.sinkDown(index * 2 + 2);
}
}
}
front() {
return this.arr[0];
}
size() {
return this.arr.length;
}
}
interface Data {
index: number;
value: number;
}
class StockPrice {
priceArr: number[];
maxPriorityQueue: PriorityQueue1<{ index: number; value: number }>;
minPriorityQueue: PriorityQueue1<{ index: number; value: number }>;
constructor() {
this.priceArr = [];
this.maxPriorityQueue = new PriorityQueue1({
compare: (a: Data, b: Data) => a.value - b.value,
});
this.minPriorityQueue = new PriorityQueue1({
compare: (a: Data, b: Data) => b.value - a.value,
});
}
update(timestamp: number, price: number): void {
this.priceArr[timestamp] = price;
this.maxPriorityQueue.enqueue({ index: timestamp, value: price });
this.minPriorityQueue.enqueue({ index: timestamp, value: price });
}
current(): number {
return this.priceArr[this.priceArr.length - 1];
}
maximum(): number {
while (
this.maxPriorityQueue.front().value !==
this.priceArr[this.maxPriorityQueue.front().index]
) {
this.maxPriorityQueue.dequeue();
}
return this.maxPriorityQueue.front().value;
}
minimum(): number {
while (
this.minPriorityQueue.front().value !==
this.priceArr[this.minPriorityQueue.front().index]
) {
this.minPriorityQueue.dequeue();
}
return this.minPriorityQueue.front().value;
}
}
|