目录

  1. 概述
  2. 插入
  3. 例题
  4. 总结

概述

❓什么是单调栈？

单调栈即满足单调性的栈结构，是对栈结构的进一步限制，规定栈顶元素是最大（小）的元素

✨能够获取到一个元素，左边离它最近的比它大的元素以及右边离他最近比它大的元素，传统做法是 $O(n^2)$，单调栈的时间花费是 $O(n)$

插入

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。例如，栈中自顶向下的元素为 ${\{4,11,45,81\}}$

插入元 $14$ 时为了保证单调性需要依次弹出元素${0,11}$，操作后栈变为${\{14,45,81\}}$

伪代码如下：

1
2
3
4
insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)

例题

  1. 典型的例题：给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

力扣链接：503. 下一个更大元素 II

  1. 如果存在一个正数数组，数组中累积和与最小值的乘积，称为指标 A，给定一个数组，请返回子数组中，指标 A 最大的值

通过单调栈，获取每个元素的左右最邻近小值信息，随后遍历整个数组，即可得出期望的 A 指标

总结

回到最初的问题，当构建完一个单调栈后（无重复值），当一个元素要弹出单调栈时，左边离它最近比它大的，就是单调栈中它压的那个元素，右边离它最近比它大的元素就是当前入栈的元素或不存在（已经遍历完成数组，右边不存在比它大的元素）

如果存在重复值，单调栈中存放的不再是值，而是一个具有相同值的链表（里面依旧存在索引）。当一个元素要出栈时，左边离它最近比它大的元素索引，就是在单调栈中它压着的链表中的最后一个元素

如果是单独考虑右边离他最近比它大的，或者左边最近离他比它大的，可以简单的使用单调栈不用考虑是否存在重复值，但如果同时需要获取左边和右边的最邻近最值信息，就需要考虑重复值的问题