LeetCode：股票价格 系列 价格跨度、价格波动（C++）

本文主要是介绍LeetCode：股票价格 系列 价格跨度、价格波动（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

901. 股票价格跨度

2034. 股票价格波动

---

本篇为股票系列的最后一篇，前两篇如下：

LeetCode：买卖股票的最佳时机 系列Ⅰ、Ⅱ、Ⅲ、Ⅳ（C++）_Cosmoshhhyyy的博客-CSDN博客

LeetCode：买卖股票 系列 含冷冻期、含手续费（C++）-CSDN博客

901. 股票价格跨度

题目描述：

        设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。

当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

• 例如，如果未来 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 次

实现代码与解析：

暴力模拟

class StockSpanner {
public:vector<int> stocks;StockSpanner() {}int next(int price) {stocks.push_back(price);int count = 0;for (int i = stocks.size() - 1; i >= 0 && stocks[i] <= price; i--) {count++;}return count;}
};/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner* obj = new StockSpanner();* int param_1 = obj->next(price);*/

原理思路：

        数据比较水，可以直接暴力模拟，下面介绍正经单调栈写法。

单调栈

class StockSpanner {
public:stack<pair<int, int>> stk; // pair<每天价格, 符合条件的个数>StockSpanner() {}int next(int price) {int count = 1;while (stk.size() && price >= stk.top().first) {count += stk.top().second;stk.pop();}stk.push(pair(price, count));return count;}
};

原理思路：

        stack中pair，记录当日金额，和此金额符合条件的个数。

        单调栈，每次当日金额大于等于栈顶，就不断出栈，同时当前个数加上栈顶日期价格符合体条件的个数，直到小于。就将当日价格入栈。也就是说栈一直是单调递减的。

        理解单调栈，最好是自己带入样例模拟一遍就懂了。

关于单调栈的解析和题目练习如下：

        Leetcode：84. 柱状图中最大的矩形（单调栈C++）_Cosmoshhhyyy的博客-CSDN博客

Leetcode：496. 下一个更大元素 I、503. 下一个更大元素 II（单调栈C++）-CSDN博客

Leetcode：42. 接雨水（单调栈C++）-CSDN博客

2034. 股票价格波动

题目描述：

        给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。

不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正 前一条错误的记录。

请你设计一个算法，实现：

• 更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将 更正 之前的错误价格。
• 找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
• 找到当前记录里股票的 最高价格 。
• 找到当前记录里股票的 最低价格 。

请你实现 StockPrice 类：

• StockPrice() 初始化对象，当前无股票价格记录。
• void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
• int current() 返回股票 最新价格 。
• int maximum() 返回股票 最高价格 。
• int minimum() 返回股票 最低价格 。

示例 1：

输入：
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
输出：
[null, null, null, 5, 10, null, 5, null, 2]解释：
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // 时间戳为 [1] ，对应的股票价格为 [10] 。
stockPrice.update(2, 5);  // 时间戳为 [1,2] ，对应的股票价格为 [10,5] 。
stockPrice.current();     // 返回 5 ，最新时间戳为 2 ，对应价格为 5 。
stockPrice.maximum();     // 返回 10 ，最高价格的时间戳为 1 ，价格为 10 。
stockPrice.update(1, 3);  // 之前时间戳为 1 的价格错误，价格更新为 3 。// 时间戳为 [1,2] ，对应股票价格为 [3,5] 。
stockPrice.maximum();     // 返回 5 ，更正后最高价格为 5 。
stockPrice.update(4, 2);  // 时间戳为 [1,2,4] ，对应价格为 [3,5,2] 。
stockPrice.minimum();     // 返回 2 ，最低价格时间戳为 4 ，价格为 2 。

提示：

• 1 <= timestamp, price <= 109
• update，current，maximum 和 minimum 总 调用次数不超过 105 。
• current，maximum 和 minimum 被调用时，update 操作 至少 已经被调用过 一次 。

实现代码与解析：

两个哈希

class StockPrice {
public:unordered_map<int, int> map;multiset<int> prices;int curtime;StockPrice() {curtime = 0;}void update(int timestamp, int price) {curtime = max(curtime, timestamp);if (map.count(timestamp)) { // 如果已经有此时间了int t = map[timestamp]; // 获取之前此时间的金额auto it = prices.find(t); // 查到此金额位置if (it != prices.end()) { // 存在，删除prices.erase(it);}}map[timestamp] = price;prices.emplace(price);}int current() {return map[curtime];}int maximum() {return *prices.rbegin();}int minimum() {return *prices.begin();}
};/*** Your StockPrice object will be instantiated and called as such:* StockPrice* obj = new StockPrice();* obj->update(timestamp,price);* int param_2 = obj->current();* int param_3 = obj->maximum();* int param_4 = obj->minimum();*/

原理思路：

        map<int, int> 记录<时间，价格>

        multiset<int> 记录每个时间的价格，方便查找最大和最小值，注意价格是可重复的，不要直接用set。

        每次更新股票价格之前，先看是否是最新，然后判断此时间是否已经存在，若存在，将multiset中的上一次对应金额删除。最后更新map。

这篇关于LeetCode：股票价格 系列 价格跨度、价格波动（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---