901. 股票价格跨度

题目描述

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

股票在某一天的 价格跨度 是指：从当天开始向前，连续的股票价格小于或等于当天价格的最大天数。

例如，如果股票过去四天的价格为 [7,2,1,2]，今天的价格为 2，那么今天的价格跨度为 3，因为从今天开始向前，有连续 3 天的股票价格小于或等于 2。
同样，如果股票过去四天的价格为 [7,34,1,2]，今天的价格为 8，那么今天的价格跨度为 3，因为从今天开始向前，有连续 3 天的股票价格小于或等于 8。

实现 StockSpanner 类：

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

示例 1：

输入
["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⁵
最多会调用 10⁴ 次 next。

解法

方法一：单调栈

思考

每次查询若从当日向前扫描，直到遇到更大价格，则调用次数较多时合计为平方级。已经被更早价格覆盖的连续段不必重算：若栈顶价格不超过当日 \(price\)，其跨度可以并入当日。

为此维护价格从栈底到栈顶单调递减的栈，元素为 \((price, cnt)\)。弹出并累加后入栈，每个价格至多进出一次，单次查询均摊常数。

根据题目描述，我们可以知道，对于当日价格 \(price\)，从这个价格开始往前找，找到第一个比这个价格大的价格，这两个价格的下标差 \(cnt\) 就是当日价格的跨度。

这实际上是经典的单调栈模型，找出左侧第一个比当前元素大的元素。

我们维护一个从栈底到栈顶价格单调递减的栈，栈中每个元素存放的是 \((price, cnt)\) 数据对，其中 \(price\) 表示价格，而 \(cnt\) 表示当前价格的跨度。

出现价格 \(price\) 时，我们将其与栈顶元素进行比较，如果栈顶元素的价格小于等于 \(price\)，则将当日价格的跨度 \(cnt\) 加上栈顶元素的跨度，然后将栈顶元素出栈，直到栈顶元素的价格大于 \(price\)，或者栈为空为止。

最后将 \((price, cnt)\) 入栈，返回 \(cnt\) 即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是调用 next(price) 的次数。

Python3JavaC++GoTypeScriptRust

class StockSpanner:
    def __init__(self):
        self.stk = []

    def next(self, price: int) -> int:
        cnt = 1
        while self.stk and self.stk[-1][0] <= price:
            cnt += self.stk.pop()[1]
        self.stk.append((price, cnt))
        return cnt


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

class StockSpanner {
    private Deque<int[]> stk = new ArrayDeque<>();

    public StockSpanner() {
    }

    public int next(int price) {
        int cnt = 1;
        while (!stk.isEmpty() && stk.peek()[0] <= price) {
            cnt += stk.pop()[1];
        }
        stk.push(new int[] {price, cnt});
        return cnt;
    }
}

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

class StockSpanner {
public:
    StockSpanner() {
    }

    int next(int price) {
        int cnt = 1;
        while (!stk.empty() && stk.top().first <= price) {
            cnt += stk.top().second;
            stk.pop();
        }
        stk.emplace(price, cnt);
        return cnt;
    }

private:
    stack<pair<int, int>> stk;
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

type StockSpanner struct {
    stk []pair
}

func Constructor() StockSpanner {
    return StockSpanner{[]pair{}}
}

func (this *StockSpanner) Next(price int) int {
    cnt := 1
    for len(this.stk) > 0 && this.stk[len(this.stk)-1].price <= price {
        cnt += this.stk[len(this.stk)-1].cnt
        this.stk = this.stk[:len(this.stk)-1]
    }
    this.stk = append(this.stk, pair{price, cnt})
    return cnt
}

type pair struct{ price, cnt int }

/**
 * Your StockSpanner object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Next(price);
 */

class StockSpanner {
    private stk: number[][];

    constructor() {
        this.stk = [];
    }

    next(price: number): number {
        let cnt = 1;
        while (this.stk.length && this.stk.at(-1)[0] <= price) {
            cnt += this.stk.pop()[1];
        }
        this.stk.push([price, cnt]);
        return cnt;
    }
}

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

use std::collections::VecDeque;
struct StockSpanner {
    stk: VecDeque<(i32, i32)>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl StockSpanner {
    fn new() -> Self {
        Self {
            stk: vec![(i32::MAX, -1)].into_iter().collect(),
        }
    }

    fn next(&mut self, price: i32) -> i32 {
        let mut cnt = 1;
        while self.stk.back().unwrap().0 <= price {
            cnt += self.stk.pop_back().unwrap().1;
        }
        self.stk.push_back((price, cnt));
        cnt
    }
}

901. 股票价格跨度

题目描述

解法

方法一：单调栈

评论