前言

• 大家好，我是新人简书博主：「 个人主页」主要分享程序员生活、编程技术、* * 以及每日的LeetCode刷题记录，欢迎大家关注我，一起学习交流，谢谢！
• 正在坚持每日更新LeetCode每日一题，发布的题解有些会参考其他大佬的思路(参考资料的链接会放在最下面)，欢迎大家关注我 ~ ~ ~
• 同时也在进行其他专项类型题目的刷题与题解活动，相关资料也会同步到「GitHub」上面 ~
• 今天是坚持写题解的27天(haha，从21年圣诞节开始的)，大家一起加油

• 每日一题：LeetCode：2034股票价格波动
  • 时间：2022-01-23
  • 力扣难度：Medium
  • 个人难度：Medium-
  • 数据结构：数组、哈希表、有序集合

2022-01-23：LeetCode.2034股票价格波动

1. 题目描述

• 题目：原题链接

  • 给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的价格 。
  • 不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。
  • 某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录更正前一条错误的记录。
  • 请你设计一个算法，实现：
    • 更新股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将更正之前的错误价格。
    • 找到当前记录里最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
    • 找到当前记录里股票的最高价格 。
    • 找到当前记录里股票的最低价格 。
  • 请你实现 StockPrice 类：
    • StockPrice() 初始化对象，当前无股票价格记录。
    • void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
    • int current() 返回股票 最新价格 。
    • int maximum() 返回股票 最高价格 。
    • int minimum() 返回股票 最低价格 。
  • 1 <= timestamp, price <= 10^9
  • update，current，maximum 和 minimum 总 调用次数不超过 10^5 。
  • current，maximum 和 minimum 被调用时，update 操作 至少 已经被调用过 一次 。

2. 方法：哈希表 & 有序集合

• 思路

  • 本题为设计题，针对各个功能逐一分析实现

  • 更新价格：通过时间戳更新价格，可以使用哈希表来存储时间戳-价格 K-V 对，然后添加元素时，判断key时间戳是否相同，更新相同时间戳的value价格

  • 最新价格

    • 既可以排序来找到最大时间戳，也可以通过维护一个大顶堆，堆顶元素就是最大时间戳，然后通过最大时间戳去哈希表中查询价格即可
    • 使用排序要额外话线性对数级时间复杂度，而使用大顶堆也需要线性额外空间，我们可以只使用一个变量来记录最大时间戳，在进行更新操作时同步更新该值

  • 最大、最小价格：有序集合

    • 通过有序集合，如TreeMap来存放价格-个数 K-V 对，因为有序集合可以实现自然排序或者定制排序，就可以得到最大最小值
    • 要注意的是，每次进行更新操作的同时，需要对有序集合同步更新，即如果一个价格被替换了，那么有序集合中该价格的个数要减一，如果个数为0了，表示该价格不存在，需要移除该元素

  • 最大、最小价格：堆、优先队列

    • 使用有序集合，是在更新操作中删除有序集合中过期的价格，如果大量调用更新操作的话，相对而言效率不高
    • 所以也可以在获取最大最小值的时候才进行过期价格的删除，类似Redis的惰性删除，即延迟删除
    • 此时，通过两个堆来存放价格，一个是大顶堆、一个是小顶堆，分别对应最大最小价格，因为此时需要判断价格是否过期，所以堆中存储的是价格和时间戳，通过时间戳在哈希表中查询价格，判断价格是否一致来判断是否过期
    • 如果已经过期，就将堆顶的元素移除，然后判断新的堆顶元素，直到不过期位置

• 题解：哈希表 & 有序集合 TreeMap

  public class StockPrice {
      int maxTimeStamp;
      Map<Integer, Integer> timeStampMap;
      TreeMap<Integer, Integer> priceMap;
  
      public StockPrice() {
          maxTimeStamp = 0;
          timeStampMap = new HashMap<>();
          priceMap = new TreeMap<>();
  
      }
  
      public void update(int timestamp, int price) {
          maxTimeStamp = Math.max(maxTimeStamp, timestamp);
          int oldPrice = timeStampMap.getOrDefault(timestamp, -1);
          timeStampMap.put(timestamp, price);
          // 更新 TreeMap
          if (oldPrice != -1) {
              priceMap.put(oldPrice, priceMap.get(oldPrice) - 1);
              if (priceMap.get(oldPrice) == 0) priceMap.remove(oldPrice);
          }
          priceMap.put(price, priceMap.getOrDefault(price, 0) + 1);
      }
  
      public int current() {
          return timeStampMap.get(maxTimeStamp);
      }
  
      public int maximum() {
          return priceMap.lastKey();
      }
  
      public int minimum() {
          return priceMap.firstKey();
      }
  
  }
  

• 题解：哈希表 & 堆

  class StockPrice {
      int maxTimeStamp;
      Map<Integer, Integer> timeStampMap;
      PriorityQueue<int[]> maxDeap;
      PriorityQueue<int[]> minDeap;
  
      public StockPrice() {
          maxTimeStamp = 0;
          timeStampMap = new HashMap<>();
          minDeap = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
          maxDeap = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
      }
  
      public void update(int timestamp, int price) {
          maxTimeStamp = Math.max(maxTimeStamp, timestamp);
          timeStampMap.put(timestamp, price);
          maxDeap.add(new int[]{price, timestamp});
          minDeap.add(new int[]{price, timestamp});
      }
  
      public int current() {
          return timeStampMap.get(maxTimeStamp);
      }
  
      public int maximum() {
          while (!maxDeap.isEmpty()) {
              int price = maxDeap.peek()[0];
              int timeStamp = maxDeap.peek()[1];
              if(timeStampMap.get(timeStamp) == price) return price;
              maxDeap.poll();
          }
          return -1;
      }
  
      public int minimum() {
          while (!minDeap.isEmpty()) {
              int price = minDeap.peek()[0];
              int timeStamp = minDeap.peek()[1];
              if(timeStampMap.get(timeStamp) == price) return price;
              minDeap.poll();
          }
          return -1;
      }
  
  }
  

• 复杂度分析：n 是更新操作的次数，复杂度依赖使用的数据结构

  • 时间复杂度
    • 构造方法：
    • update()：，因为更新了TreeMap或将元素添加到了优先队列，此时会排序
    • current()：
    • maximum()、minimum()：，对于TreeMap，查询最大值最小值是二分对数级；对于优先队列，虽然查询是常数级，但是因为还要判断价格是否过期，平均下来约为对数级
  • 空间复杂度：

最后

如果本文有所帮助的话，欢迎大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的其他平台，上面会更新Java面经、八股文、刷题记录等等，欢迎大家光临交流，谢谢！

• 「个人博客」
• 「掘金」
• 「LeetCode」