901. Online Stock Span

Leetcode link

题目简介

var StockSpanner = function() {

};

/** 
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function(price) {

};

题目要求我们实现一个 StockSpanner 类，该类支持一个 next 方法

next 方法能够得到当天的股票价格，我们需要返回当天之前小于等于这个价格的天数有几天

解题思路

这一题有两个思路

最简单的思路就是我们用一个数组保存所有天数的股价，然后每次 next 都由后往前遍历计算天数

或者我们可以用一个单调递增栈 stack 来保存过去股价以及对应的天数 [price, span]，这样能减少上一个方法的时间复杂度

Javascript

var StockSpanner = function() {
    // [price, span]
    this.stack = []
};

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

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

复杂度分析

时间

O(n)

空间

O(n)