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

901. 股票价格跨度

题意

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

解法 暴力 + 优化

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

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

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

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

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

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

• 如果 $prices[i]<=price$，那么，$spans[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 单调栈

由于这道题的本质就是寻找 $price$ 左侧第一个大于 $price$ 的元素，所以显然可以使用单调递减栈来解答。

为了获取跨度，再在栈中存储一个 $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)$。

---