2034. 股票价格波动

给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。

不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正 前一条错误的记录。

请你设计一个算法，实现：

更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将 更正 之前的错误价格。
找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
找到当前记录里股票的 最高价格 。
找到当前记录里股票的 最低价格 。
请你实现 StockPrice 类：

StockPrice() 初始化对象，当前无股票价格记录。
void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
int current() 返回股票 最新价格 。
int maximum() 返回股票 最高价格 。
int minimum() 返回股票 最低价格 。

---

  思路：本题主要使用了TreeMap。TreeMap大部分用法与HashMap类似。

  TreeMap 是 Java 中的一个基于红黑树（Red-Black Tree）实现的有序映射（Map）数据结构。它扩展了 AbstractMap 类，并实现了 NavigableMap 和 SortedMap 接口，因此具有有序性和排序功能。以下是关于 TreeMap 的详细介绍：
  特点和用途：

• 有序性： TreeMap 内部使用红黑树数据结构来维护键值对的有序性。这意味着元素在 TreeMap 中按照键的顺序排列，你可以根据键的自然顺序或提供的比较器来排序元素。

• 键的唯一性： TreeMap 中不允许重复的键。如果尝试插入一个已经存在的键，新值会覆盖旧值。

• 高效的查找： 由于红黑树的特性，TreeMap 具有快速的查找性能。根据键查找值的时间复杂度为 O(log n)，其中 n 是元素的数量。

• 支持导航和范围查询： TreeMap 提供了一些方法，如 firstKey()、lastKey()、lowerKey()、higherKey() 等，用于在有序集合中导航和执行范围查询。

• 实现了 NavigableMap 和 SortedMap 接口： 这使得 TreeMap 可以用于一些高级的操作，例如获取子映射、反转映射等。

基本操作示例：
下面是使用 TreeMap 的一些基本操作示例：

import java.util.*;public class TreeMapExample {public static void main(String[] args) {// 创建一个 TreeMapTreeMap<String, Integer> treeMap = new TreeMap<>();// 插入键值对treeMap.put("apple", 3);treeMap.put("banana", 2);treeMap.put("cherry", 5);treeMap.put("date", 1);// 遍历 TreeMapfor (Map.Entry<String, Integer> entry : treeMap.entrySet()) {String key = entry.getKey();int value = entry.getValue();System.out.println("Key: " + key + ", Value: " + value);}// 查找键对应的值int value = treeMap.get("banana"); // 返回 2// 删除键值对treeMap.remove("cherry");}
}

注意事项：
  TreeMap 的键必须是可比较的，要么具有自然顺序，要么提供了比较器。
  在使用自定义对象作为键时，需要确保自定义对象实现了 Comparable 接口或在构造 TreeMap 时提供了比较器。
  TreeMap 不是线程安全的，如果需要在多线程环境中使用，应该考虑使用 ConcurrentSkipListMap。
  总之，TreeMap 是一个有序的、高效的键值对数据结构，适用于需要按键排序的场景。它提供了丰富的操作方法，允许进行导航、范围查询和高效查找。

class StockPrice {/**思路：使用一个HashMap与一个TreeMapHashMap存储时间戳与价格TreeMap存储价格与是该价格的天数*/HashMap<Integer, Integer> hashMap = new HashMap();TreeMap<Integer, Integer> treeMap = new TreeMap();int curDay = -1;public StockPrice() {}public void update(int timestamp, int price) {if(curDay<timestamp) {curDay = timestamp;}if(hashMap.containsKey(timestamp)) {// 需要更新int old = hashMap.get(timestamp);int cnt = treeMap.get(old); if(cnt == 1) {treeMap.remove(old);} else {treeMap.put(old, cnt-1);}}hashMap.put(timestamp, price);treeMap.put(price, treeMap.getOrDefault(price, 0)+1);}public int current() {return hashMap.get(curDay);}public int maximum() {return treeMap.lastKey();}public int minimum() {return treeMap.firstKey();}
}/*** Your StockPrice object will be instantiated and called as such:* StockPrice obj = new StockPrice();* obj.update(timestamp,price);* int param_2 = obj.current();* int param_3 = obj.maximum();* int param_4 = obj.minimum();*/