适用场景

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了

那么单调栈的原理是什么呢？为什么时间复杂度是 O(n) 就可以找到每一个元素的右边第一个比它大的元素位置呢？

单调栈的本质是空间换时间，遍历的过程中每一个元素都和栈顶的元素进行比较, 如果比栈顶的元素小就入栈, 如果比栈顶的元素大:

1. 说明找到了比栈顶元素大的第一个元素
2. 循环栈顶, 把所有比当前元素小的栈元素都弹出, 并记录当前元素为他们右边第一个比他大的元素

在使用单调栈的时候首先要明确如下几点：

单调栈里存放的元素是什么？

单调栈里只需要存放元素的下标 i 就可以了，如果需要使用对应的元素，直接 T[i] 就可以获取。

单调栈里元素是递增呢？ 还是递减呢？

注意以下讲解中，顺序的描述为 从栈头到栈底的顺序

如果要找数组右边第一个比当前元素大的元素, 那么单调栈从栈顶到栈低是递增的.

使用单调栈主要有三个判断条件。

• 当前遍历的元素 T[i] 小于栈顶元素 T[st.top()] 的情况
• 当前遍历的元素 T[i] 等于栈顶元素 T[st.top()] 的情况
• 当前遍历的元素 T[i] 大于栈顶元素 T[st.top()] 的情况

把这三种情况分析清楚了，也就理解透彻了

遍历顺序问题

顺序遍历, 单调递增, 可以找到右边第一个更大的元素

逆序遍历, 单调递减, 同样可以找到右边第一个更大的元素

只要在入栈、出栈的逻辑上处理好就可以了

关于单调栈的顺序给大家一个总结： 739. 每日温度 (opens new window) 中求一个元素右边第一个更大元素，单调栈就是递增的，84.柱状图中最大的矩形 (opens new window) 求一个元素右边第一个更小元素，单调栈就是递减的。