901. 股票价格跨度

🟠 🔖 栈 设计 数据流 单调栈 🔗 力扣open in new window LeetCodeopen in new window

题目

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.

The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
Also, if the prices of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days.

Implement the StockSpanner class:

StockSpanner() Initializes the object of the class.
int next(int price) Returns the span of the stock's price given that today's price is price.

Example 1:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]
Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85); // return 6

Constraints:

1 <= price <= 10^5
At most 10^4 calls will be made to next.

题目大意

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

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

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

实现 StockSpanner 类：

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

示例：

输入：
["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^5
最多调用 next 方法 10^4 次

解题思路

可以使用 单调递减栈 来高效地解决问题。

定义一个单调栈，用于存储 [价格, 索引]，并保持栈中价格按从高到低的顺序排列。
每次加入一个新价格时，从栈顶开始，如果栈顶的价格小于等于当前价格，弹出栈顶（这些较小的价格已包含在跨度中）。
剩下的栈顶元素（如果有）对应的是最近一次比当前价格更高的价格的索引。
计算跨度：
- 如果栈为空，跨度就是 当前索引 + 1（所有价格都不超过当前价格）。
- 如果栈不为空，跨度就是 当前索引 - 栈顶索引。
将当前价格和索引压入栈。
返回跨度。

复杂度分析

时间复杂度：O(n)，其中 n 是 next 被调用的次数，每个价格最多进栈和出栈一次。
空间复杂度：O(n)，栈最多存储 n 个价格。

代码

var StockSpanner = function () {
	this.stack = []; // 单调递减栈，存储 [price, index]
	this.idx = -1; // 当前价格的索引
};

/**
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function (price) {
	this.idx++;
	// 弹出栈中所有小于等于当前价格的元素
	while (
		this.stack.length > 0 &&
		this.stack[this.stack.length - 1][0] <= price
	) {
		this.stack.pop();
	}
	// 计算跨度
	const span =
		this.stack.length == 0
			? this.idx + 1
			: this.idx - this.stack[this.stack.length - 1][1];
	// 将当前价格和索引压入栈
	this.stack.push([price, this.idx]);
	return span;
};

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

901. 股票价格跨度

# 901. 股票价格跨度

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

901. 股票价格跨度

题目

题目大意

解题思路

复杂度分析

代码

相关题目