问题

Link

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

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

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

实现 StockSpanner 类：

StockSpanner() 初始化类对象。

int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

难度：一般

思路

  1. 一维数组的第一个小于/大于问题应该用单调栈解法；
  2. 定义一个递减单调栈，每个元素是索引与price的二元组；
  3. 每次返回栈顶元素与该元素索引差。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var StockSpanner = function () {
	this.stack = [[-1, Number.MAX_VALUE]];
	this.index = -1;
};

/**
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function (price) {
	this.index++;
	while (this.stack.slice(-1)[0][1] <= price) {
		this.stack.pop();
	}
	let res = this.index - this.stack.slice(-1)[0][0];
	this.stack.push([this.index, price]);
	return res;
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * var obj = new StockSpanner()
 * var param_1 = obj.next(price)
 */