Sponsored
Sponsored
This approach utilizes a HashMap to store the price corresponding to each timestamp and a SortedMap to dynamically maintain the counts of each price, enabling efficient tracking of maximum and minimum prices. The HashMap allows quick updates and access to any timestamp's price, while the SortedMap keeps track of occurrences of each price value.
Time Complexity: Update operation is O(log n), as updating the SortedDict requires logarithmic time. Current, maximum, and minimum operations are O(1).
Space Complexity: O(n), where n is the number of timestamps since we store each timestamp and its price.
1#include <unordered_map>
2#include <map>
3
4class StockPrice {
5public:
6 StockPrice() : latest_time(0) {}
7
8 void update(int timestamp, int price) {
9 if (priceMap.find(timestamp) != priceMap.end()) {
10 int oldPrice = priceMap[timestamp];
11 priceCounts[oldPrice]--;
12 if (priceCounts[oldPrice] == 0) {
13 priceCounts.erase(oldPrice);
14 }
15 }
16 priceMap[timestamp] = price;
17 priceCounts[price]++;
18 latest_time = std::max(latest_time, timestamp);
19 }
20
21 int current() {
22 return priceMap[latest_time];
23 }
24
25 int maximum() {
26 return priceCounts.rbegin()->first;
27 }
28
29 int minimum() {
30 return priceCounts.begin()->first;
31 }
32
33private:
34 std::unordered_map<int, int> priceMap;
35 std::map<int, int> priceCounts;
36 int latest_time;
37};Like the Python solution, we utilize two data structures in C++: an unordered_map for storing timestamps and their respective prices, and a map (ordered map) for tracking price frequencies. Updating involves checking if a record already exists for a timestamp, adjusting frequency counts, and updating the latest timestamp if needed. We then use map's properties to get the maximum and minimum prices efficiently.
This approach uses a max heap (priority queue) for tracking the maximum price and a min heap for the minimum prices. Updates ensure that any obsolete prices are removed, and heap roots can quickly provide max/min prices. Furthermore, checks against the current timestamp allow discarding outdated entries efficiently.
Time Complexity: Update is O(log n) due to heap operations. Maximum and minimum operations may require O(log n) adjustments.
Space Complexity: O(n)
1import heapq
2
3class StockPrice
In this solution, we maintain maxHeap for potential maximum prices and minHeap for potential minimum prices. Each update involves pushing the price to both heaps. Current retrieval from heaps requires cleaning invalid top entries until top reflects a valid timestamp. Thus, maximum and minimum methods traverse heap roots for the latest price associations using a heap invariant.