美容店网站建设,学校学院网站建设目标,阿里巴巴运营每天必做,网站模板插件一、前言
本题基于leetcode901股票价格趋势这道题#xff0c;说一下通过java解决的一些方法。并且解释一下笔者写这道题之前的想法和一些自己遇到的错误。需要注意的是#xff0c;该题最多调用 next 方法 10^4 次,一般出现该提示说明需要注意时间复杂度。
二、解决思路
①…一、前言
本题基于leetcode901股票价格趋势这道题说一下通过java解决的一些方法。并且解释一下笔者写这道题之前的想法和一些自己遇到的错误。需要注意的是该题最多调用 next 方法 10^4 次,一般出现该提示说明需要注意时间复杂度。
二、解决思路
①栈排序存在超出时间限制问题
其实笔者做这道题之前并不知道单调栈这一东西第一时间想到的是很像之前做过的和栈相关的一道题–栈排序毕竟都是类似按照某一顺序对栈元素进行排序。需要借用辅助栈而考虑到它需要计算的是连续天数不是一个简单的排序。 拿这道题给的示例输入来说 思路就是如果是空栈那么我们直接放就好。 而当不是空栈时此时通过price和栈顶元素的差值区分情况 ①小于0 说明price要小那么我们直接入栈然后由于此时栈肯定没有比price更小的元素所以只有它自己return 1即可 ②大于等于0 说明此时price要大于栈顶元素由于它要的是最大连续日数从今天开始往回数包括今天那么我必须得保持入栈的一个顺序否则就不是连续的而是一个比当前price要小的所有天数这样一个结果。 那么怎样处理呢我们可以先将该price入辅助栈然后再从栈顶遍历将小于等于当前price的栈元素弹出push到辅助栈中。此时记录辅助栈的size就是我们要返回的最大连续天数最后再将辅助栈一次push到我们的主栈中即可。 我这边画一个图 如上图第一次入栈70这个元素时比栈顶元素60要大将price70入辅助栈然后遍历主栈栈顶将小于等于70的元素弹出栈然后push进辅助栈此时记录辅助栈size为2然后将辅助栈元素全部弹出并且推入主栈最后返回size即可。且这样不会修改我主栈元素的原本顺序就是按照next元素的顺序进行排序的就也顺便解决了连续这个问题。 同理后面入75如下图所示 代码如下
class StockSpanner {private StackInteger stockStack;private StackInteger diffStack;public StockSpanner() {stockStack new Stack();diffStack new Stack();}public int next(int price) {if (stockStack.isEmpty()) {stockStack.push(price);return 1;} else {int diff price - stockStack.peek();if (diff 0) {stockStack.push(price);return 1;} else {diffStack.push(price);while (!stockStack.isEmpty() stockStack.peek() price) {diffStack.push(stockStack.pop());}int res diffStack.size();while (!diffStack.isEmpty()) {stockStack.push(diffStack.pop());}return res;}}}
}好像这样思路确实没什么问题运行发现超出时间限制o(╥﹏╥)o
虽说时间复杂度是O(n)可是这样的操作确实还是非常繁琐的且还需要借助辅助栈且最后主栈的元素量是Next()的调用次数无效或者其实用不上的元素根本没有pop出栈导致浪费了很多空间。 所以也就有了后面一种方法–单调栈该方法不再需要辅助栈且不会浪费额外空间。
②单调栈
我们将每一个股票价格想象成java的一个对象它拥有它的id拥有它的价格我们可以使用一个int[]去承装他们int[0]装idint[1]装价格。 然后我们可以想象下我们需要比今日股票要小于等于的天数是否就是将这些对象给按照一个单调递减的顺序排序如果放入的元素比上一个元素要小此时结果就是当前放入元素的下标id和上一个元素下标的差值。如果要大此时不符合单调递减那么我需要将比它小的元素全部抹去让我们承装对象的结构始终符合单调递减此时结果是当前当如元素的下标id和抹去后的它的上一个元素下标id的差值。 为了方便我们后续程序少一些空栈之类的判断我们初始化的时候可以先push进一个id为0价格是Integer.MAX的元素这样到时候我们出栈也不用担心会导致空栈。 而对于next方法首先是下标这个很好理解我们每次调用next方法时id即可很像我们数据库的ID自增策略。由于我们需要的是小于或等于今天价格的最大连续日数所以是一个单调递减栈如果要插入的price大于栈顶元素此时将单调栈的元素依次弹出并且此时将当前price对应的下标减去出栈后的栈顶元素的下标这个下标差就是我们需要返回的结果。然后再将当前元素入栈即可然后返回下标差即可。 仍然拿示例1举例 当我插入100-80-60,由于每次插入都比栈顶元素要小而当插入70时此时比栈顶元素60要大从栈顶开始遍历一直到栈顶元素大于price为止此时出栈完后栈顶是id2,price80这个元素然后记录res4-22,然后将price70,id4这个元素入栈。 放入60,75同理 代码如下
class StockSpanner {private Dequeint[] stockStack;private int id;public StockSpanner() {stockStack new ArrayDeque();stockStack.push(new int[]{0,Integer.MAX_VALUE});id 0;}public int next(int price) {id ;while (price stockStack.peek()[1]){stockStack.pop();}int ret id - stockStack.peek()[0];stockStack.push(new int[]{id, price});return ret;}
}三、栈排序和单调栈的区别
那么其实栈排序和单调栈是有明显区别的这里做一个总结
单调栈单调栈是一种特殊的栈结构其插入时保证栈内元素的单调性。通常用于解决数组中下一个更大或下一个更小元素的问题。例如我们可以见我们力扣496下一个更大元素 I这道题单调栈需要维护一个单调递增或单调递减的栈顶元素序列每当新元素插入时都需要判断该元素与栈顶元素的大小关系不断弹出栈顶元素直到满足单调性。
栈排序栈排序是对栈内元素进行递增或递减排序的一种思路。通常使用额外的栈来辅助排序。将原始栈的元素依次弹出插入到辅助栈中的正确位置最后将辅助栈中的元素重新压回原始栈中从而实现了栈排序。需要注意的是仅使用原始栈是无法实现栈排序的因为栈的弹出顺序一旦改变就无法恢复。
总体来说单调栈和栈排序都是基于栈实现的常用算法思路但其应用场景和实现方法不同。单调栈通常用于解决比较问题需要维护栈内元素的单调性而栈排序则是对栈内元素的排序需要额外借助辅助栈实现。
