本文主要是介绍【LeetCode - 每日一题】901. 股票价格跨度(23.10.07),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
901. 股票价格跨度
题意
- 设计一个数据结构
- 返回股票当日价格的跨度(必须是当日开始的)
解法 暴力 + 优化
一开始没理解题意,以为是求第 i
天及以前,小于等于 prices[i]
的最大连续子串的长度。后来才发现,这个最大连续子串必须包含当天。
所以问题就转换成了:从右往左寻找第一个大于 prices[i]
的数。
第一个想法是暴力。也就是对于每一天,从右往左遍历,寻找第一个大于 prices[i]
的数。
但是,注意数据范围为 O ( n 5 ) O(n^5) O(n5) ,并且调用操作的数量级为 O ( n 4 ) O(n^4) O(n4),而暴力的时间复杂度为 O ( n 2 ) O(n^2) O(n2),必定超时。
需要进行优化。既然要优化,那么 能够利用的只有当天以前的答案(因为每一天都要计算,答案是动态累积的)。
设:数组 prices[]
维护股票每一天的价格,数组 spans[]
维护每一天的答案。又注意到,若 s p a n s [ i ] = k spans[i] = k spans[i]=k,那么也就是说, p r i c e s [ i − k + 1 ] − p r i c e s [ i ] prices[i - k +1] - prices[i] prices[i−k+1]−prices[i] 都将小于等于 p r i c e s [ i ] prices[i] prices[i],也就是说, s p a n s [ i ] spans[i] spans[i] 实际上维护了一个区间的最大值。
那么,假设股票的当天价格为 p r i c e price price,从右向左遍历数组 prices[]
:
- 如果 p r i c e s [ i ] < = p r i c e prices[i] <= price prices[i]<=price,那么, s p a n s [ i ] spans[i] spans[i] 维护的这样一个区间都将小于等于 p r i c e price price,所以将其并入;
- 如果 p r i c e s [ i ] > p r i c e prices[i] > price prices[i]>price,那么,这个最大连续子串被截断,此时 最大连续子串的长度就是要求返回的答案。
class StockSpanner {
public:StockSpanner() {}int next(int price) {int ans = 1, tmp = 0;int idx = prices.size() - 1;if(idx == -1){prices.emplace_back(price);spans.emplace_back(1);return 1;}if(prices[idx] > price){ans = max(ans, tmp);idx--;tmp = 0;}else{if(idx == prices.size() - 1) tmp = 1;while(idx >= 0 && prices[idx] <= price){tmp += spans[idx];idx -= spans[idx];}}ans = max(ans, tmp);prices.emplace_back(price);spans.emplace_back(ans);return ans;}
private:vector<int> prices, spans;
};/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner* obj = new StockSpanner();* int param_1 = obj->next(price);*/
复杂度
时间复杂度:不会算 :)
空间复杂度:不会算 :)
解法2 单调栈
由于这道题的本质就是寻找 p r i c e price price 左侧第一个大于 p r i c e price price 的元素,所以显然可以使用单调递减栈来解答。
为了获取跨度,再在栈中存储一个 i d x idx idx 信息。
class StockSpanner {
public:StockSpanner(): size(0) {}int next(int price) {pair<int, int> cur(price, ++size);pair<int, int> tmp(0, 0);while(!st.empty() && st.top().first <= price) st.pop();if(!st.empty()) tmp = st.top();st.push(cur);return cur.second - tmp.second;}
private:stack<pair<int, int> > st;int size;
};/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner* obj = new StockSpanner();* int param_1 = obj->next(price);*/
复杂度
时间复杂度: O ( n ) O(n) O(n)。
空间复杂度: O ( n ) O(n) O(n)。
这篇关于【LeetCode - 每日一题】901. 股票价格跨度(23.10.07)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!