LeetCode:股票价格 系列 价格跨度、价格波动(C++)

2023-10-11 04:20

本文主要是介绍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
  • updatecurrentmaximum 和 minimum  调用次数不超过 105 。
  • currentmaximum 和 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++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/185472

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)