901. 股票价格跨度
编写一个 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。原站题解
php 解法, 执行用时: 188 ms, 内存消耗: 30.5 MB, 提交时间: 2023-10-07 10:48:13
class StockSpanner {
private $stockPrice = [];
private $stockRes = [];
public function construct()
{
}
/**
* @param Integer $price
* @return Integer
*/
function next($price) {
$i = sizeof($this->stockPrice) - 1;
$res = 1;
while ($i >= 0 && $price >= $this->stockPrice[$i]) {
$res += $this->stockRes[$i];
$i -= $this->stockRes[$i];
}
array_push($this->stockPrice, $price);
array_push($this->stockRes, $res);
return $res;
}
}
/**
* Your StockSpanner object will be instantiated and called as such:
* $obj = StockSpanner();
* $ret_1 = $obj->next($price);
*/
golang 解法, 执行用时: 120 ms, 内存消耗: 7.6 MB, 提交时间: 2023-10-07 07:34:02
type StockSpanner struct {
stack [][2]int
idx int
}
func Constructor() StockSpanner {
return StockSpanner{[][2]int{{-1, math.MaxInt32}}, -1}
}
func (s *StockSpanner) Next(price int) int {
s.idx++
for price >= s.stack[len(s.stack)-1][1] {
s.stack = s.stack[:len(s.stack)-1]
}
s.stack = append(s.stack, [2]int{s.idx, price})
return s.idx - s.stack[len(s.stack)-2][0]
}
/**
* Your StockSpanner object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Next(price);
*/
javascript 解法, 执行用时: 256 ms, 内存消耗: 53.4 MB, 提交时间: 2023-10-07 07:33:45
var StockSpanner = function() {
this.stack = [];
this.stack.push([-1, Number.MAX_VALUE]);
this.idx = -1;
};
/**
* @param {number} price
* @return {number}
*/
StockSpanner.prototype.next = function(price) {
this.idx++;
while (price >= this.stack[this.stack.length - 1][1]) {
this.stack.pop();
}
let ret = this.idx - this.stack[this.stack.length - 1][0];
this.stack.push([this.idx, price]);
return ret;
};
/**
* Your StockSpanner object will be instantiated and called as such:
* var obj = new StockSpanner()
* var param_1 = obj.next(price)
*/
cpp 解法, 执行用时: 172 ms, 内存消耗: 82.8 MB, 提交时间: 2023-10-07 07:33:18
class StockSpanner {
public:
StockSpanner() {
this->stk.emplace(-1, INT_MAX);
this->idx = -1;
}
int next(int price) {
idx++;
while (price >= stk.top().second) {
stk.pop();
}
int ret = idx - stk.top().first;
stk.emplace(idx, price);
return ret;
}
private:
stack<pair<int, int>> stk;
int idx;
};
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner* obj = new StockSpanner();
* int param_1 = obj->next(price);
*/
java 解法, 执行用时: 20 ms, 内存消耗: 53.2 MB, 提交时间: 2023-10-07 07:33:01
class StockSpanner {
Deque<int[]> stack;
int idx;
public StockSpanner() {
stack = new ArrayDeque<int[]>();
stack.push(new int[]{-1, Integer.MAX_VALUE});
idx = -1;
}
public int next(int price) {
idx++;
while (price >= stack.peek()[1]) {
stack.pop();
}
int ret = idx - stack.peek()[0];
stack.push(new int[]{idx, price});
return ret;
}
}
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner obj = new StockSpanner();
* int param_1 = obj.next(price);
*/
java 解法, 执行用时: 57 ms, 内存消耗: 53.6 MB, 提交时间: 2023-10-07 07:32:37
class StockSpanner {
Stack<Integer> prices, weights;
public StockSpanner() {
prices = new Stack();
weights = new Stack();
}
public int next(int price) {
int w = 1;
while (!prices.isEmpty() && prices.peek() <= price) {
prices.pop();
w += weights.pop();
}
prices.push(price);
weights.push(w);
return w;
}
}
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner obj = new StockSpanner();
* int param_1 = obj.next(price);
*/
python3 解法, 执行用时: 344 ms, 内存消耗: 19.7 MB, 提交时间: 2022-10-21 09:58:24
class StockSpanner:
def __init__(self):
self.stack = [(-1, inf)]
self.idx = -1
def next(self, price: int) -> int:
self.idx += 1
while price >= self.stack[-1][1]:
self.stack.pop()
self.stack.append((self.idx, price))
return self.idx - self.stack[-2][0]
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)