力扣每日一题2022-01-23中等题：股票价格波动

力扣每日一题2022-01-23中等题：股票价格波动

股票价格波动

2034.股票价格波动

题目描述思路

哈希表+有序集合

Java实现Python实现

---

2034.股票价格波动 题目描述

股票价格波动

---

思路 哈希表+有序集合

根据题意，需要记录特定时间戳的股票价格、返回最新股票价格以及返回最高和最低价。
由于同一个时间戳可能出现多次，所以后面的记录会覆盖前面的记录，因此可以使用哈希表记录每个时间戳对应的股票价格。
对于返回股票最新价格的 *** 作，可以维护最大的时间戳，用最大的时间戳在哈希表中查找，可以得到最新的股票价格。
对于返回股票最高价和最低价的 *** 作，需要找到哈希表中的最高和最低价。可以使用有序集合维护哈希表中的股票价格，有序集合中的最大值和最小值即为当前哈希表中的股票的最高和最低价格。
因此，StockPrice类需要包含最大时间戳、哈希表和有序集合。初始化时，最大时间戳设为0，哈希表和有序集合设为空。
对于更新 *** 作：

从哈希表得到时间戳timestamp对应的原价格，如果哈希表中没有时间戳timestamp对应的原价格，则将原价格记为0（由于实际价格都大于0，因此可以将原价格记为0表示哈希表中没有改时间戳）；将哈希表中时间戳timestamp对应的价格更新为新价格price；如果原价格大于0，即之前已经有时间戳timestamp对应的记录，则将原价格从有序集合中删除；在有序集合中加入新价格price。
其余 *** 作可以直接从哈希表和有序集合中得到结果：对于返回最新价格，从哈希表中得到最大时间戳对应的股票价格并返回即可；对于返回最高价格，从有序集合中返回最高价格即可；对于返回最低价格，从有序集合中返回最低价格即可。 Java实现

class StockPrice {
    int maxTimeStamp;
    HashMap timePriceMap;
    TreeMap prices;

    public StockPrice() {
        maxTimeStamp = 0;
        timePriceMap = new HashMap<>();
        prices = new TreeMap<>();
    }
    
    public void update(int timestamp, int price) {
        maxTimeStamp = Math.max(timestamp, maxTimeStamp);
        int prevPrice = timePriceMap.getOrDefault(timestamp, 0);
        timePriceMap.put(timestamp, price);
        if (prevPrice > 0) {
            prices.put(prevPrice, prices.get(prevPrice) - 1);
            if (prices.get(prevPrice) == 0) {
                prices.remove(prevPrice);
            }
        }
        prices.put(price, prices.getOrDefault(price, 0) + 1);
    }
    
    public int current() {
        return timePriceMap.get(maxTimeStamp);
    }
    
    public int maximum() {
        return prices.lastKey();
    }
    
    public int minimum() {
        return prices.firstKey();
    }
}

Python实现

from sortedcontainers import SortedList
class StockPrice:

    def __init__(self):
        self.maxTimeStamp = 0
        self.timePriceMap = {}
        self.prices = SortedList()


    def update(self, timestamp: int, price: int) -> None:
        if timestamp in self.timePriceMap:
            self.prices.discard(self.timePriceMap[timestamp])
        self.prices.add(price)
        self.timePriceMap[timestamp] = price
        self.maxTimeStamp = max(self.maxTimeStamp, timestamp)
        

    def current(self) -> int:
        return self.timePriceMap[self.maxTimeStamp]


    def maximum(self) -> int:
        return self.prices[-1]


    def minimum(self) -> int:
        return self.prices[0]



# Your StockPrice object will be instantiated and called as such:
# obj = StockPrice()
# obj.update(timestamp,price)
# param_2 = obj.current()
# param_3 = obj.maximum()
# param_4 = obj.minimum()