【C++单调栈】901. 股票价格跨度|1708

本文涉及的基础知识点

C++单调栈

LeetCode901. 股票价格跨度

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来 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 <= 10⁵
最多调用 next 方法 10⁴ 次

单调栈

从小到大处理第i天，从i-1到0，寻找第一天股价大于今天，令其为j，则第i天最长连续日为i-j。
处理price[i]时：
i1 < i2 < i，如果price[i1] < price[i2] 则i1被淘汰i2淘汰。淘汰后，价格严格递减。
淘汰后，栈顶元素就是j，如果栈顶为空,j就是-1。

代码

核心代码

class StockSpanner {
public:
StockSpanner() {

}

int next(int price) {
while (m_sta.size() && (price >= m_nums[m_sta.top()])) {
m_sta.pop();
}
const int left = m_sta.empty() ? -1 : m_sta.top();
m_sta.emplace(m_nums.size());
m_nums.emplace_back(price);
return m_nums.size() - 1 - left;
}
vector<int> m_nums;
stack<int> m_sta;
};

单元测试

vector<int> nums;
TEST_METHOD(TestMethod11)
{
nums = {100,80,60,70,60,75,85};
StockSpanner stockSpanner;
vector<int> res;
for (const auto& n : nums) {
res.emplace_back(stockSpanner.next(n));
}
AssertEx(vector<int>{1, 1, 1, 2, 1, 4, 6}, res);
}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

原文地址：https://blog.csdn.net/he_zhidan/article/details/142466333

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！