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:
    stackint, 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 记录<时间，价格>

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

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