基础算法 (六) --单调栈

将夜将行:
单调栈个人理解总结： 1.单调栈是用来解决这一类问题：寻找数组中元素其左或者右第一个大于或小于该元素的值。 2.首先，如果要寻找其右侧，要从右向左遍历。反之，从左向右遍历。 3.如果是寻找第一个大于该元素的值，则要在栈顶保存较小的值。即从栈底到栈顶是递减的（栈顶到栈底就是递增的）。如果寻找第一个小于该元素的值，则要在栈顶保存较大的值。从栈底到栈顶是递增的。 4.以上，还需要刷题融会贯通，我也是刚刚才学，如果有错欢迎交流指出。

【回复】这几天刷了一些题，感觉开始的理解有些浅显和局限了。单调栈需要明确，我们想要获得的结果。不论是维护递增栈还是递减栈，在保持顺序入栈时，我们可以获得什么；在破坏单调顺序时，我们可以获得什么。 举例说明：如果我们想要获得一个数组中，其左和右第一个小于其的元素的索引。按最初的理解，需要从左到右和从右到左分别遍历一次。但是如果继续深入考虑一下： 如果从左到右遍历，维护一个单调递增的顺序，如果正常入栈的时候，显然我们可以获取入栈元素左边第一个小于其的索引。（栈顶元素小于当前元素，如果栈为空，则说明左侧没有小于当前元素的值）当破坏了栈的单调递增顺序，显然，我们可以获取出栈元素右边第一个小于该元素的索引。综上，只需一次遍历便可同时确定。 需要掌握本质，灵活应用。（我现在也做不到，要继续努力）
【回复】回复 @将夜将行 :是的 这周末刷的时候看到有从前往后 从后往前都可以做的写法 其实都可以 关键还是理清楚需要得到什么样的递增和递减关系决定
chopinFredriccc:
Labuladong的视频版太赞啦！看文字看的很吃力～

DefTnT123:
想请问Up,视频中最后的例题leetcode84，为什么最后还要对栈进行一轮操作？我在看Leetcode题解的时候，其他人是在数据前后加0。请问这样做的原因是什么。个人不是很理解为什么在leetcode84最后要清空栈，而之前的例题则少了这一步操作。

【回复】https://www.bilibili.com/video/BV1dY4y1q7tL 可以看一下这个，我觉得他讲清楚了构造单调栈的意义，也能够理解最后清空栈的含义