【力扣】单调栈:901. 股票价格跨度

2023-10-08 04:45

本文主要是介绍【力扣】单调栈:901. 股票价格跨度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【力扣】单调栈:901. 股票价格跨度

文章目录

  • 【力扣】单调栈:901. 股票价格跨度
    • 1. 题目介绍
    • 2. 思路
    • 3. 解题代码
    • 参考

1. 题目介绍

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

  • 当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始往回数,包括今天)。
  • 例如,如果未来 7 天股票的价格是 [100,80,60,70,60,75,85],那么股票跨度将是 [1,1,1,2,1,4,6] 。

代码实现 StockSpanner 类:

  • StockSpanner() 初始化类对象。

  • int next(int price) 给出今天的股价 price ,返回该股票当日价格的 跨度 。

  • 示例:
    在这里插入图片描述

2. 思路

调用 next 时,

  • 输入是新的一天的股票价格,
  • 需要返回包含此日在内的,往前数最多有连续多少日的股票价格是小于等于今日股票价格的个数。

如果把每日的 price 当成数组不同下标的值,即需要求出每个值与上一个更大元素之间的下标之差。这种题目可以用单调栈求解,具体原理如下:

  • 单调栈是一种和单调队列类似的数据结构。
    • 单调队列主要用于解决滑动窗口问题,
    • 单调栈则主要用于解决NGE问题(Next Greater Element),也就是,对序列中每个元素,找到下一个比它大的元素。(当然,“下一个”可以换成“上一个”,“比它大”也可以换成“比他小”,原理不变。)
  • 这比单调队列还简单一点。
    • 我们维护一个栈,表示“待确定NGE的元素”,然后遍历序列。
    • 当我们碰上一个新元素,我们知道,越靠近栈顶的元素离新元素位置越近。
    • 所以不断比较新元素与栈顶,如果新元素比栈顶大,则可断定新元素就是栈顶的NGE,于是弹出栈顶并继续比较。直到新元素不比栈顶大,再将新元素压入栈。显然,这样形成的栈是单调递减的。

此题的具体解法:
栈的元素可以是股票价格的下标(即天数)和股票价格的二元数对,并且在栈中先插入一个天数为 0 天,最大值作为价格的二元数对,来保证栈不会为空。调用 next 时,先将栈中价格小于等于此时 price 的元素都弹出,直到遇到一个大于 price 的值,并将 price 入栈,计算下标差返回。

3. 解题代码

class StockSpanner {
private:stack<pair<int, int>> stackp; int ts;
public:StockSpanner() {this->stackp.emplace(0, INT_MAX);this->ts = 0;}int next(int price) {ts++;while (price >= stackp.top().second) {stackp.pop();	// 出栈}int res = ts - stackp.top().first;stackp.emplace(ts, price);	// 入栈return res;}
};

参考

【1】https://leetcode.cn/problems/online-stock-span/

这篇关于【力扣】单调栈:901. 股票价格跨度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

双指针(5)_单调性_有效三角形的个数

个人主页:C++忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创 双指针(5)_单调性_有效三角形的个数 收录于专栏【经典算法练习】 本专栏旨在分享学习C++的一点学习笔记,欢迎大家在评论区交流讨论💌 目录 1. 题目链接: 2.题目描述 : 3.解法 :     解法一(暴力枚举) :     算法思路 :     代码展示 : 暴力枚

力扣 797. 所有可能路径【DFS】

1. 题目 2. 代码 DFS , 直接见代码 class Solution {public:vector<int> path;vector<vector<int>> res; // 结果集void dfs(vector<vector<int>>& graph, int cur, int n){// 找出所有从节点 0 到节点 n-1 的路径// 下标从 0 开始的if (

机器学习模型中的因果关系:引入单调约束

单调约束是使机器学习模型可行的关键,但它们仍未被广泛使用欢迎来到雲闪世界。 碳ausality 正在迅速成为每个数据科学家工具包中必不可少的组成部分。 这是有充分理由的。 事实上,因果模型在商业中具有很高的价值,因为它们为“假设”情景提供了更可靠的估计,特别是在用于做出影响业务结果的决策时。 在本文中,我将展示如何通过简单的更改(实际上添加一行代码)将传统的 ML 模型(如随机森林、L