【LeetCode - 每日一题】901. 股票价格跨度（23.10.07）

本文主要是介绍【LeetCode - 每日一题】901. 股票价格跨度（23.10.07），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

901. 股票价格跨度

题意

设计一个数据结构
返回股票当日价格的跨度（必须是当日开始的）

解法暴力 + 优化

一开始没理解题意，以为是求第 i 天及以前，小于等于 prices[i] 的最大连续子串的长度。后来才发现，这个最大连续子串必须包含当天。

所以问题就转换成了：从右往左寻找第一个大于 prices[i] 的数。

第一个想法是暴力。也就是对于每一天，从右往左遍历，寻找第一个大于 prices[i] 的数。
但是，注意数据范围为 $O(n^5)$ ，并且调用操作的数量级为 $O(n^4)$ ，而暴力的时间复杂度为 $O(n^2)$ ，必定超时。

需要进行优化。既然要优化，那么 能够利用的只有当天以前的答案（因为每一天都要计算，答案是动态累积的）。

设：数组 prices[] 维护股票每一天的价格，数组 spans[] 维护每一天的答案。又注意到，若 $s p an s [i] = k$ ，那么也就是说， $p r i ces [i - k + 1] - p r i ces [i]$ 都将小于等于 $p r i ces [i]$ ，也就是说， $s p an s [i]$ 实际上维护了一个区间的最大值。

那么，假设股票的当天价格为 $p r i ce$ ，从右向左遍历数组 prices[]:

如果 $p r i ces [i] <= p r i ce$ ，那么， $s p an s [i]$ 维护的这样一个区间都将小于等于 $p r i ce$ ，所以将其并入；
如果 $p r i ces [i] > p r i ce$ ，那么，这个最大连续子串被截断，此时 最大连续子串的长度就是要求返回的答案。

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 ce$ 左侧第一个大于 $p r i ce$ 的元素，所以显然可以使用单调递减栈来解答。

为了获取跨度，再在栈中存储一个 $i d x$ 信息。

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);*/