【2022-10-21每日一题】901. 股票价格跨度[Medium]
2022-10-21
2分钟阅读时长
2022-10-21每日一题：901. 股票价格跨度
难度：Medium
标签：栈 、 设计 、 数据流 、 单调栈
编写一个 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) 小于或等于今天的价格。
提示：
- 调用
StockSpanner.next(int price)时，将有1 <= price <= 10^5。 - 每个测试用例最多可以调用
10000次StockSpanner.next。 - 在所有测试用例中，最多调用
150000次StockSpanner.next。 - 此问题的总时间限制减少了 50%。
方法一：单调栈
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
go
type StockSpanner struct {
stack [][2]int
idx int
}
func Constructor() StockSpanner {
return StockSpanner{[][2]int{{-1, math.MaxInt32}}, -1}
}
func (this *StockSpanner) Next(price int) int {
this.idx++
// 维护递减单调栈
for price >= this.stack[len(this.stack)-1][1] {
this.stack = this.stack[:len(this.stack)-1]
}
this.stack = append(this.stack, [2]int{this.idx, price})
return this.idx-this.stack[len(this.stack)-2][0]
}
/**
* Your StockSpanner object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Next(price);
*/
php
class StockSpanner {
private $prices = [];
private $weights = [];
function __construct() {
$this->prices = [];
$this->weights = [];
}
/**
* @param Integer $price
* @return Integer
*/
function next($price) {
$w = 1;
while ($this->prices && end($this->prices) <= $price) {
array_pop($this->prices);
$w += array_pop($this->weights);
}
$this->prices[] = $price;
$this->weights[] = $w;
return $w;
}
}
/**
* Your StockSpanner object will be instantiated and called as such:
* $obj = StockSpanner();
* $ret_1 = $obj->next($price);
*/
复杂度分析
时间复杂度：O(n)，其中 n 为调用 next 函数的次数，每个 price 值最多都会入栈出栈各 1 次。
空间复杂度：O(n)，栈中最多有 n 个元素。