1.什么是单调栈（Monotone Stack）

单调栈是一种特殊的栈，它的特点是栈中的元素始终保持单调有序。通常有两种单调栈，分别是单调递增栈和单调递减栈。

单调递增栈顾名思义，栈内元素从栈底到栈顶递增有序，即栈顶元素最大，栈底元素最小。

而单调递减栈则相反，栈内元素从栈底到栈顶递减有序，即栈顶元素最小，栈底元素最大。

2.应用场景

使用到单调栈的力扣

力扣84

https://leetcode.cn/problems/largest-rectangle-in-histogram/solutions/108083/84-by-ikaruga/?envType=study-plan-v2&envId=top-100-liked

单调栈的主要应用场景是求解某个元素的左边或者右边第一个比它大或者小的元素。

从左到右遍历元素数组：

  • 如果新的元素比栈顶元素大，就入栈

  • 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小，再加入该新元素

效果：

  • 栈内的元素是递增的

  • 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素

    • 举个例子，配合下表，现在索引在 6 ，栈里是 1 5 6 。
      接下来新元素是 2 ，那么 6 需要出栈。
      当 6 出栈时，右边 2 代表是 6 右边第一个比 6 小的元素。

  • 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素

    • 当 6 出栈时，5 成为新的栈顶，那么 5 就是 6 左边第一个比 6 小的元素。

nums = [2,1,5,6,2,3]

也就是说当index为6时，5是左边第一个比他小的，2是右边第一个比他小的元素。