单调栈是什么？

保证以下规则的数据结构称为单调栈，可以使用Stack或ArrayDeque等实现

  1. 栈中元素要么是严格递增的,要么是严格递减的。

  2. 每个元素入栈时,都会保持栈的单调性。

单调栈可以解决什么问题？

  1. 寻找一个数组中每个元素左边/右边第一个比它大/小的元素。

  2. 寻找一个数组中每个元素左边/右边第一个比它大/小的元素的索引。

  3. 计算一个数组中每个元素左边/右边第一个比它大/小的元素的值的差。

例如739.每日温度这种题，对于求当前元素左边或右边第一个比当前元素大或小的元素的位置，此类问题均可以采用单调栈的思路来做

单调栈的主要特点

  1. 可以在线性时间内解决上述问题,时间复杂度为O(n)。

  2. 通过维护栈的单调性,可以快速找到每个元素左/右边第一个满足条件的元素。

  3. 适用于处理需要考虑左/右邻近元素信息的问题。

基本实现思路

单调栈的基本实现可以分为以下几个步骤：

  1. 初始化一个空栈和一个结果数组。

  2. 遍历输入数组,对于每个元素:

    • 当栈不为空且当前元素满足单调性条件时,不断弹出栈顶元素并记录结果。

    • 将当前元素压入栈。

  3. 处理栈中剩余元素,给它们赋予默认值(通常为-1)。

  4. 返回最终的结果数组。

单调性条件condition(cur, top)需要根据具体问题进行定义。例如,对于找左边第一个比当前元素大的,条件可以是cur > top。

更简单的来说，单调栈的基本规则就是一句话（以单调递增栈为例）：

就是如果要入栈的元素比栈顶元素大，更新此时栈顶元素下标对应的结果，然后弹出去，如果还比栈顶元素大，还一直弹，直到没有比他大的了，然后入栈

相关刷题文章

739. 每日温度

文章地址：leetcode-739. 每日温度

496. 下一个更大元素 I

文章地址：leetcode-496. 下一个更大元素 II

503. 下一个更大元素 II

文章地址：leetcode-503. 下一个更大元素 II

402. 移掉 K 位数字

文章地址：leetcode-402. 移掉K位数字

901. 股票价格跨度

文章地址：leetcode-901. 股票价格跨度

84. 柱状图中最大的矩形

42. 接雨水

239. 滑动窗口最大值