锐客网

  1. 首页 > it技术 > >

笔记|单调栈详解-基于LeetCode的题目

算法leetcode笔记职场和发展题解

单调栈的意思可以看这个链接，这位大佬写的很详细https://blog.csdn.net/liujian20150808/article/details/50752861
或者也可以直接看我的讲解：
单调栈，可以理解为有单调性的一个数组，在这里我们可以理解成为栈数组，栈数组可以是单调增，也可以是单调减，在本题中我们使用的是单调增即栈数组从0到数组最后是单调递增的。单调栈的数组性质也是我们常用的性质，到这里为止，我们对单调栈有了基本印象，一个单调递的数组
从栈底到栈顶，单调递增，可以理解为从栈数组的0位置开始到栈数组的最后一位一直是单调递增。



**单调栈的性质：**接下来我们分析单调栈的性质，因为单调栈是即栈数组是单调递增的，因此他的单调性必须一直保持，因此在遇到下一个需要插入
栈数组的值的时候，我们首先判断该值与栈顶元素相比那个大？我们设栈顶元素为a，需要插入的值为b，当a ，我们可以设原来的栈数组为[0 , a],0到a单调递增，符合单调栈的要求
1：a 2：a>b的时候 b无法直接压入栈，因为那样会破坏栈的单调性我们需要将a弹出栈，然后再将b压入栈，栈数组就会变成[0 , b]




**扩展-举例：我们扩展来讲，如果原来的栈数组为[0 , 1 , 5 , 8] ，可以看出栈顶元素为8，我们需要将9压入栈的话，因为9>8,所以压入之后栈数组变成[0 , 1 , 5 , 8 , 9]不影响原来的单调性，依然是单调递增。但是如果我们需要将4压入栈的话，我们需要先将大于4的值弹出栈，整个过程是这样的，先将要压入栈的值与当前的栈顶元素比较，即4与8比较。因为4<8，所以4无法压入栈，因此我们要弹出8，弹出8之后栈数组变成[0 , 1 , 5],然后4继续与栈顶元素5比较，因为4<5，因此我们需要弹出5，弹出之后栈顶数组变成[0 , 1],然后4与栈顶元素1比较，因为4>1，因此4可以压入栈，压入之后栈数组变成[0 , 1 , 4]
这就是单调栈的思想，把他变成数组来讲就很好理解-单调减的栈反过来理解即可（我想我已经表达的很清楚，不懂的可以在评论里指出来，我看到会回复解答的）
举例用法的话可以看我上一条博客，对于LeetCode的困难题求最大矩形面积写的题解，很详细
【笔记|单调栈详解-基于LeetCode的题目】或者看我LeetCode写的题解力扣

    推荐阅读


    上一篇：笔记|LeetCode每日一题题解（1189. “气球” 的最大数量）

    下一篇：python中的多线程