数据结构 单调栈

应用情景

求当前元素 前面/后面，第一个比它 小/大 的元素的 值/下标/下标距离

优点

剔除重复寻路操作，将暴力 O(n^2) 优化到 O(n)

性质

从栈底开始，元素 单调递增/单调递减

单调性视具体情景而定 (找较大值还是较小值、找的方向)

思路

以某种形式存放遍历过的元素，使该种存放形式符合情景要求

讨论当前元素与栈顶元素比较大小后的几种情况分别对应什么操作

实现

按遍历顺序生成结果：

1.存放每一个遍历过的元素 (写在循环体最后)

2.对于当前元素，要知道有没有比它 大/小 的，就从栈顶向下找，不满足条件的直接出栈

因为对于之后还没遍历到的元素，栈顶不满足条件的元素和当前元素相比

一定劣于当前元素，不会再用到了

3.经历过 2. 之后，当前栈一定符合条件：若栈为空，则没有元素比当前元素更 小/大

若栈非空，则栈顶元素一定是第一个比当前元素 小/大 的

按其他顺序生成结果：略 (我遇到的题目都是按遍历顺序生成结果更优)

注意事项

注意讨论遍历方向，有时反着遍历，思路和代码更简洁

栈中元素有时候需要存数值，有时候要存下标，视题目要求而定

例题

LeetCode.739.每日温度

题目与题解：

题解 力扣 LeetCode 739 每日温度 C++-CSDN博客https://blog.csdn.net/qwq_ovo_pwp/article/details/143243618?spm=1001.2014.3001.5501