网站与建设实训报告,动画制作平台,wordpress json rest api,杭州新站整站seo题目链接 Leetcode.901 股票价格跨度 Rating #xff1a; 1709 题目描述
设计一个算法收集某些股票的每日报价#xff0c;并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数#xff08;从今天开始往回数#xff0c;…题目链接 Leetcode.901 股票价格跨度 Rating 1709 题目描述
设计一个算法收集某些股票的每日报价并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数从今天开始往回数包括今天。
例如如果未来 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 提示
1price1051 price 10^51price105最多调用 next方法 10410^4104 次
分析
使用一个 单调栈stack栈里面存的是 (price,idx)组成的二元组里面只记录大于当前 price的二元组。
如果当前栈顶的二元组的price 当前price就将栈顶元素弹出。这样操作之后要么栈为空要么栈顶元素就是左边第一个大于当前 price的二元组了。
用当前的 idx减去栈顶元素的 idx栈为空就减去 -1差值就是当前 price的跨度。
时间复杂度O(n)O(n)O(n)
C代码
using PII pairint,int;
class StockSpanner {
public:int idx 0;stackPII stk; StockSpanner() {}int next(int price) {while(!stk.empty() stk.top().first price) stk.pop();int l stk.empty() ? -1 : stk.top().second;int ans idx - l;stk.push({price,idx});return ans;}
};Java代码
class StockSpanner {int idx;Stackint[] stk;public StockSpanner() {idx 0;stk new Stack();}public int next(int price) {while(!stk.isEmpty() stk.peek()[0] price) stk.pop();int l stk.isEmpty() ? -1 : stk.peek()[1];int ans idx - l;stk.push(new int[]{price,idx});return ans;}
}
