摘要:前言的第二道题目,同样是分值分且中等难度的题目股票价格跨度编写一个类,它收集某些股票的每日报价,并返回该股票当日价格的跨度。第二版股票价格跨度存储一个递增数列的实体最低位最高位在当前股价区间内最高位大于当前股价,生成一个新的
前言
Weekly Contest 101的第二道题目,同样是分值4分且中等难度的题目股票价格跨度:
解题思路编写一个StockSpanner类,它收集某些股票的每日报价,并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始往回数,包括今天)。
例如,如果未来7天股票的价格是[100, 80, 60, 70, 60, 75, 85],那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
示例:
输入:["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]] 输出:[null,1,1,1,2,1,4,6] 解释: 首先,初始化 S = StockSpanner(),然后: S.next(100) 被调用并返回 1, S.next(80) 被调用并返回 1, S.next(60) 被调用并返回 1, S.next(70) 被调用并返回 2, S.next(60) 被调用并返回 1, S.next(75) 被调用并返回 4, S.next(85) 被调用并返回 6。 注意 (例如) S.next(75) 返回 4,因为截至今天的最后 4 个价格 (包括今天的价格 75) 小于或等于今天的价格。提示:
调用StockSpanner.next(int price) 时,将有1 <= price <= 10^5。
每个测试用例最多可以调用10000次StockSpanner.next。
在所有测试用例中,最多调用150000次StockSpanner.next。
此问题的总时间限制减少了50%。
这道题目其实如果只是实现题目的功能要求的话是一道很简单的题目。只是不断获取一个数组从最后一个元素开始单调递增数列的长度。
但是有由于在提示内容中已经提到了执行时间限制的问题,就可以知道这个题目需要进行执行时间相关方面的优化。最终我决定使用的优化方案是参考跳表这种数据结构,利用空间换取时间。思路大致如下,详细内容可以参考实现代码的第二版:
定义一个存储递增数列的实体StockPrices,该实体还会记录最高位(第一个元素)和最低位(最后一个元素)
StockSpanner中存储的是StockPrices的数组
每当有新股价进入,逆序(从最后一个元素开始)遍历StockSpanner的StockPrices数组。然后根据是否在当前的递增数列的范围进行处理。
以示例作为例子:
初始化后
pricesList:[ { left:0 right:0 prices:[] }
next(100)
pricesList:[ { left:100 right:100 prices:[100] } return 1
next(80)
pricesList:[ { left:100 right:100 prices:[100] }, { left:80 right:80 prices:[80] }] return 1
next(60)
pricesList:[ { left:100 right:100 prices:[100] }, { left:80 right:80 prices:[80] } { left:60 right:60 prices:[60] }] return 1
next(70)
pricesList:[ { left:100 right:100 prices:[100] }, { left:80 right:80 prices:[80] }, { left:60 right:70 prices:[60,70] }] return 2
next(60)
pricesList:[ { left:100 right:100 prices:[100] }, { left:80 right:80 prices:[80] }, { left:60 right:70 prices:[60,70] }, { left:60 right:60 prices:[60] }] return 1
next(75)
pricesList:[ { left:100 right:100 prices:[100] }, { left:80 right:80 prices:[80] }, { left:60 right:70 prices:[60,70] }, { left:60 right:75 prices:[60,75] }] return 4
next(85)
pricesList:[ { left:100 right:100 prices:[100] }, { left:80 right:80 prices:[80] }, { left:60 right:70 prices:[60,70] }, { left:60 right:85 prices:[60,75,85] }] return 6实现代码 第一版
这个版本是只实现功能的版本,所以提交上去基本都是执行超时的结果。但是可以作为第二版的参考。
class StockSpanner { private List第二版prices; public StockSpanner() { prices=new ArrayList (); } public int next(int price) { int result=1; prices.add(price); int days=prices.size(); if(days>1){ int todayPrice=price; for(int i=days-2;i>=0;i--){ if(todayPrice>=prices.get(i)){ ++result; }else{ break; } } } return result; } }
/** * 股票价格跨度 * @author RJH * create at 2018/9/9 */ public class StockSpanner { private ListpricesList; /** * 存储一个递增数列的实体 */ class StockPrices{ /** * 最低位 */ int left; /** * 最高位 */ int right; /** * */ List prices=new ArrayList<>(); } public StockSpanner() { pricesList=new ArrayList<>(); StockPrices stockPrices=new StockPrices(); pricesList.add(stockPrices); } public int next(int price) { int result=0; StockPrices stockPrices=pricesList.get(pricesList.size()-1); List prices=stockPrices.prices; if(prices.size()==0){ stockPrices.left=price; stockPrices.right=price; prices.add(price); result+=prices.size(); return result; } if(stockPrices.right<=price){//在当前股价区间内 prices.add(price); stockPrices.right=price; result+=prices.size(); }else{//最高位大于当前股价,生成一个新的StockPrices StockPrices newStockPrices=new StockPrices(); newStockPrices.prices=new ArrayList<>(); newStockPrices.prices.add(price); newStockPrices.left=price; newStockPrices.right=price; result+=newStockPrices.prices.size(); pricesList.add(newStockPrices); } for(int i=pricesList.size()-2;i>=0;i--){ StockPrices sp=pricesList.get(i); if(sp.right>price){ break; }else if(sp.left>price){ for(int j=sp.prices.size()-1;j>=0;j--){ if(price<=sp.prices.get(j)){ ++result; } } }else if(sp.left<=price){ result+=sp.prices.size(); } } return result; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/77053.html
摘要:双指针法复杂度时间空间思路根据买卖股票的特性,我们必须先低价买,再高价卖,这个找最大收益的过程实际上是找到目前为之的最低价。我们可以利用这个之前计算的结果降低时间复杂度不过代价是额外空间,所以需要把到的最大收益存在数组中。 Best Time to Buy and Sell Stock I Say you have an array for which the ith element...
摘要:题目描述给定一个数组,它的第个元素是一支给定股票第天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。随后,在第天股票价格的时候买入,在第天股票价格的时候卖出这笔交易所能获得利润。 题目描述 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票...
摘要:贪心算法每一步必须满足一下条件可行的即它必须满足问题的约束。四题目分析贪心算法,总是做出在当前看来是最好的选择,不从整体最优上加以考虑,也就是说,只关心当前最优解,按照贪心策略,不关心以后,我们只关心当前利益。 一、写在前面 为什么要在LeetCode刷题?大家都知道不管是校招还是社招算法题是必考题,而这一部分恰巧是大多数人的短板,所以刷题首先是为了提高自身的编程能力,能够在算法面试中...
摘要:后一种方法被称之为多因子统计套利模型。套利套利可以被称为交叉资产套利的一种形式,它可以识别的价值与其相关资产之间的差异。目前,统计套利策略已经成为了对冲基金和投资银行的主要力量。 作者:chen_h微信号 & QQ:862251340微信公众号:coderpai简书地址:https://www.jianshu.com/p/ea2... 1. 什么是定量交易 定量交易是通过统计技术(或...
摘要:当然了,和具体股票对象应该是全局的变量这样才能够在别的方法中用到二验证码校验对于验证码检查我们并不会陌生,我们在学习的时候已经使用过了验证码检查了。 一、股票案例 我们要做的是股票的案例,它能够无刷新地更新股票的数据。当鼠标移动到具体的股票中,它会显示具体的信息。 我们首先来看一下要做出来的效果: showImg(https://segmentfault.com/img/remote/...
阅读 692·2021-07-25 21:37
阅读 3622·2019-08-30 15:55
阅读 2547·2019-08-30 15:54
阅读 1675·2019-08-30 15:44
阅读 3069·2019-08-30 15:44
阅读 826·2019-08-30 15:43
阅读 988·2019-08-29 15:36
阅读 3009·2019-08-29 10:58