1.题目
题目地址(901. 股票价格跨度 - 力扣（LeetCode）)
https://leetcode.cn/problems/online-stock-span/
题目描述
设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
-
例如，如果未来 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 <= 105- 最多调用
next方法104次
2.题解
2.1单调栈
思路
这里寻找股票价格小于或等于今天价格的最大连续日数, 反过来说,不成立条件就是寻找左侧最近的更大值(大于当前日股票价格,连续日数就中断了)
这里寻找左侧更大值,也就是寻找prices[stk.top()] > price, 所以反过来我们这里while执行的条件就是prices[stk.top()] <= price
我们使用了一个数组来保存之前的股票值,并且通过数组大小判断当前位置索引
1.如果栈空,说明当前股价是目前遇到的最大值,这时候其实第一个不满足条件的索引值可以看做是-1, 所以距离就是i-(-1)=i+1
2.如果栈不为空,而是遇到了某个更大的值停了下来,获得它的索引, 距离是i-index(为何不加一?因为这是第一个不满足的值,而不是最后一个满足的值)
但是这里我们额外用了一个数组,可以思考一下如何去除这个数组的使用
代码
- 语言支持：C++
C++ Code:
class StockSpanner {
public:
StockSpanner() {}
int next(int price) {
while(!stk.empty() && price >= prices[stk.top()]){
stk.pop();
}
prices.push_back(price);
int i = prices.size() - 1;
int ans = stk.empty()?(i + 1) : i - stk.top();
stk.push(i);
return ans;
}
private:
vector<int> prices;
stack<int> stk;
};
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner* obj = new StockSpanner();
* int param_1 = obj->next(price);
*/
复杂度分析
令 n 为数组长度。
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
2.2 单调栈(改进,不使用数组记录)
思路
如果不使用数组记录,我们要解决两个使用prices数组的替换
1.prices[stk.top()],我们之前栈中保存的是索引值,我们如何通过索引值获取相应值的大小?
2.int i = prices.size() - 1; 这里我们获取当前元素的索引值用的是数组大小来求的,如果不使用,该如何获取?
解决:
1.我们的栈不仅记录索引值,也记录相应值(stack中存储一个pair元素即可)
2.我们使用一个成员变量idx记录当前元素的索引值,每次操作的时候idx++即可
备注:这里还进行了一个小优化,本来我们要判断栈是否为空,这里预先往栈中添加了一个(-1,INT_MAX)保证栈不为空
代码
class StockSpanner {
public:
StockSpanner() {
this->idx = -1;
this->stk.emplace(-1,INT_MAX);
}
int next(int price) {
while(!stk.empty() && stk.top().second <= price){
stk.pop();
}
idx++;
int ans = idx - stk.top().first;
stk.emplace(idx, price);
return ans;
}
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);
*/