单调栈

单调栈

单调栈是指栈里面的元素是「递增」或者「递减」的。

单调栈的应用场景

找到数组中每个元素左右第一个比他大的数
例如，数组是 [2, 4, 3, 1]。

• 元素 2，左边没有比他大的数，右边比他大的数是 4
• 元素 4，左右都没有比他大的数
• 元素 3，左边比他大的数是 4，右边没有比他大的数
• 元素 1，左边比他大的数是 3，右边没有比他大的数

「递增栈」可以找到元素左右第一个比他小的数；
「递减栈」可以找到元素左右第一个比他大的数；

例如，为了找到 [2, 4, 3, 1]中每个元素左右比他大的数，构造「递减栈」：

• 2入栈：由于栈里面没有其他元素，因此 2左边没有比他大的元素
• 2出栈，4入栈：可知 2右边比他大的元素是 4，由于 4是栈底元素，因此 4的左边没有比他大的元素
• 3入栈：栈里面还有 4，因此 3左边比他大的元素是 4
• 1入栈：栈的下方还有 3，因此 1左边比他大的元素是 3
• 最后，4, 3, 1都没有出栈，因此没有这三个元素右边都没有比他大的

注：

• 无法用「递增栈」找出元素右边比他大的值，例如 [**3**, 2, 5]中的 3
• 无法用「递增栈」找出元素左边比他大的值，例如 [4, 2, **3**]中的 3
• 无法用「递减栈」找出元素右边比他小的值，例如 [**3**, 4, 1]中的 3
• 无法用「递减栈」找出元素左边比他小的值，例如 [2, 5, **3**]中的 3

例子：求最大的矩形面积