题目

题目来源：力扣（LeetCode）

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

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

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

示例：

输入：[“StockSpanner”,”next”,”next”,”next”,”next”,”next”,”next”,”next”], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

思路分析

我们用单调栈维护一个单调递减的价格序列，并且对于每个价格，存储一个 width 表示它离上一个价格之间（即最近的一个大于它的价格之间）的天数。如果是栈底的价格，则存储它本身对应的天数。例如 [11, 3, 9, 5, 6, 4, 7] 对应的单调栈为 (11, width=1), (9, width=2), (7, width=4)。

当我们得到了新的一天的价格，例如 10，我们将所有栈中所有小于等于 10 的元素全部取出，将它们的 width 进行累加，再加上 1 就得到了答案。在这之后，我们把 10 和它对应的 width 放入栈中，得到 (11, width=1), (10, width=7)。

  1. var StockSpanner = function () {
  2.   // 单调递减栈 priceStack 用来每天的价格
  3.   // 栈 widthStack 用来记录对应价格的跨度
  4.   // 这两个栈元素个数应该是一样的，一一对应的
  5.   this.priceStack = [];
  6.   this.widthStack = [];
  7. };
  9. /** 
  10.  * @param {number} price
  11.  * @return {number}
  12.  */
  13. StockSpanner.prototype.next = function (price) {
  14.   // 跨度至少为1，就是自身，所以这里是1，如果不包含自身，那么这里就是0
  15.   let width = 1;
  16.   // 当前的 价格 大于 priceStack 栈的栈顶元素，将栈中所有小于当前 价格的元素出栈，并将它们的跨度进行累加，再加上 1，就是当前价格的跨度
  17.   while (this.priceStack.length && price >= this.priceStack[this.priceStack.length - 1]) {
  18.     this.priceStack.pop();
  19.     width += this.widthStack.pop();
  20.   }
  21. // 把当前价格和当前价格的跨度分别放入对应的栈中
  22.   this.priceStack.push(price);
  23.   this.widthStack.push(width);
  25.   return width;
  26. };
  28. /**
  29.  * Your StockSpanner object will be instantiated and called as such:
  30.  * var obj = new StockSpanner()
  31.  * var param_1 = obj.next(price)
  32.  */

借鉴：https://leetcode-cn.com/problems/online-stock-span/solution/gu-piao-jie-ge-kua-du-dan-diao-zhan-jie-ir7kl/