代码随想录一刷笔记_单调栈

60+在408的算法考察难度和深度上还是收手了👍）

单调栈的使用场景

在一维数组中，寻找任一个元素的右边（左边）第一个比自己大（小）的元素的位置。

主要思想是用空间换时间。

时间复杂度为O(n)。

739 每日温度

方法一：双重循环

好好好，超时咯。

方法二：单调栈

需要记录两段记录，一个是当天的温度，另一个是当前是第几天。这里使用的方法是，在单调栈中存入序号，然后调用数组中的数据完成比较数值大小的任务。

这里可以细分为三种情形，情况①②是可以合并同类项的。

1. 当前遍历的元素小于栈顶元素
2. 当前遍历的元素等于栈顶元素
3. 当前遍历的元素大于栈顶元素

496 下一个更大元素Ⅰ

方法一：暴力解法

双重循环

方法二：单调栈

相比739 每日温度这一题，这里的难度体现在：我们需要处理的数组和需要应用单调栈的数组是两个数组，额外进行一次匹配操作，如果直接按照上一题的方法对先应用栈然后再额外进行匹配的话，时间复杂度实际上是和暴力解法差不多的。

所以，这里使用了哈希表的方法进行匹配，也就是预处理（死去的知识。。。。）先将数组nums1中的下标映射到数值上。在单调栈中进行判定时，判断当前的数值是否在数组nums1中存在

单调栈的三种情况：

1. 当前遍历的元素小于栈顶元素
2. 当前遍历的元素等于栈顶元素
3. 当前遍历的元素大于栈顶元素

其中，情况1、2是可以合并的，此时将遍历底元素入栈；情况3，将栈顶元素弹出，然后push入这个遍历的元素

503 下一个更大元素Ⅱ

方法一：暴力解法

方法二：单调栈

自己做的时候想复杂了属于是，我想的是循环遍历数组，当遍历到的下标与栈顶下标重合时结束遍历。但是这样存在一个问题，如果有两个最大值的话，按照单调栈的处理逻辑，这两个数据对应的下标会螺旋交替地压入栈中，死循环的情况。

所以，最优的解决方法还是遍历数组两次。