901. 股票价格跨度

901. 股票价格跨度

难度: 中等

来源: 每日一题 2023.10.07

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。

当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

• StockSpanner() 初始化类对象。
• int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

示例：

输入：
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出：
[null, 1, 1, 1, 2, 1, 4, 6]

解释：
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80);  // 返回 1
stockSpanner.next(60);  // 返回 1
stockSpanner.next(70);  // 返回 2
stockSpanner.next(60);  // 返回 1
stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85);  // 返回 6

提示：

• 1 <= price <= 10^5
• 最多调用 next 方法 10^4 次

class StockSpanner {

    public StockSpanner() {

    }
    
    public int next(int price) {

    }
}

分析与题解

• 暴力法

  暴力方案就很简单了, 我们只需要按照题目要求创建一个数组空间用来存储每日的价格, 要求该股票当日价格的 跨度 , 我们只需要倒序遍历即可.

  代码如下所示.

  class StockSpanner {
      List<Integer> cache = new ArrayList<>();
      public StockSpanner() {
  
      }
      
      public int next(int price) {
          int result = 1;
          for(int i = cache.size() - 1; i >= 0; i--) {
              if(cache.get(i) <= price) {
                  result++;
              } else {
                  break;
              }
          }
          cache.add(price);
          return result;
      }
  }
  
  /**
  * Your StockSpanner object will be instantiated and called as such:
  * StockSpanner obj = new StockSpanner();
  * int param_1 = obj.next(price);
  */
  

  复杂度分析:

  • 时间复杂度: O(n²)
  • 空间复杂度: O(n), 空间与数组的长度成线性关系.

  结果如下所示.

  

• 暴力法优化

  暴力方案其实很好理解了, 但是存在很多重复的遍历过程, 我们不妨考虑, 这样的一种情况, 当我们知道前面某天A的价格的 跨度, 那么如果后面某一天比A的价格还要高, 那么他的价格跨度区间同样适用于这一天. 如图所示.

  

  这时候, 我们可以直接跳过A的所有跨度, 从而减少遍历的次数. 如下图所示.

  

  那么我们在遍历过程中就可以增加这样的过程减少遍历次数, 但是我们需要另外创建一个数组用来保持某一天的跨度 .

  List<Integer> resultArray = new ArrayList<>();
  

  对于优化跳转的代码, 具体如下所示.

  for(int i = cache.size() - 1; i >= 0; i--) {
      if(cache.get(i) <= price) {
          result += resultArray.get(i);
          i -= resultArray.get(i) - 1;
      } else {
          break;
      }
  }
  

  接下来, 我们一起看一下整体的代码实现.

  class StockSpanner {
      List<Integer> cache = new ArrayList<>();
      List<Integer> resultArray = new ArrayList<>();
  
      public StockSpanner() {
  
      }
      
      public int next(int price) {
          int result = 1;
          for(int i = cache.size() - 1; i >= 0; i--) {
              if(cache.get(i) <= price) {
                  result += resultArray.get(i);
                  i -= resultArray.get(i) - 1;
              } else {
                  break;
              }
          }
          resultArray.add(result);
          cache.add(price);
          return result;
      }
  }
  
  /**
  * Your StockSpanner object will be instantiated and called as such:
  * StockSpanner obj = new StockSpanner();
  * int param_1 = obj.next(price);
  */
  

  复杂度分析:

  • 时间复杂度: O(n²)
  • 空间复杂度: O(2n), 空间与数组的长度成线性关系.

  结果如下所示.