微网站制作多少钱,国外html模板网站,wordpress新建音乐界面,wordpress二次开发难吗#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 单调栈 求解思路 实现代码 运行结果 共勉 题目链接
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 次 求解思路实现代码运行结果 ⚡ 单调栈 求解思路
首先这道题目我们可以通过暴力方法求解我们可以从该数左侧直接遍历找到又多少个数是小于当前的数值的。也就是遇到最大的数停止。当然如果使用暴力求解对于这道题目我们是过不了的必须要另辟蹊径啦。此时我们想要的是怎么找到某一个数左侧最大的数,那么我们就可以通过单调栈求解。需要注意的是单调栈中除了维护当前的price价格还需要维护的就是没一个价格所走的距离便于求得题目中的股票最大跨度。有了这俩个最基本的信息我们就可以求解了。还需要注意的是对于单调栈每次弹出的元素我们还需要重新加入吗答案是不需要.为什么呢因为此时的price会直接将小于它的值都干掉此时price就是最大的因此不需要维护。具体求解的过程步骤请看下面代码。 实现代码
class StockSpanner {private Stackint[] stack;private int index;public StockSpanner() {index0;stacknew Stack();}public int next(int price) {while(!stack.isEmpty()stack.peek()[1]price){stack.pop();}int prestack.isEmpty()?-1:stack.peek()[0];int disindex-pre;stack.push(new int[]{index,price});return dis;}
}/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner obj new StockSpanner();* int param_1 obj.next(price);*/运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
