单调栈

Table of Contents

定义

单调栈即满足单调性的栈结构,插入时要保证栈的单调性。

它适合解决那些需要找到 下一个/上一个更大/小值 的问题。

按照从 栈顶到栈底 的顺序,递增则为单调递增栈,递减则为单调递减栈。

左侧为栈底,右侧为栈顶:

单调递增栈:[5,4,3,2,1]

单调递减栈:[1,2,3,4,5]

对于单调栈,在 插入 时,需要去比较入栈元素和栈顶元素的大小。

以单调递增栈为例子,要保证从栈顶到栈底是递增的关系。

入栈时,要保持栈顶的元素大于等于入栈的元素。

如果栈顶元素比入栈元素小,则将栈顶元素弹出,直到栈顶元素大于等于入栈元素,或者栈为空。

性质

对于数组 [5,2,3,7,1]

按照从左到右遍历数组,构造单调递增栈(左边栈低,右边栈顶):

  • []
  • [5] 栈为空,入栈 5
  • [5,2] 栈顶 5 大于 2,入栈 2
  • [5,3] 栈顶 2 小于 3,弹出 2;弹出后,栈顶 5 大于 3,入栈 3。 观察此时的序列,通过序列可以知道,对于入栈元素 3,左边第一个比它大的元素是 5
  • [7] 栈顶 3 小于 7,弹出 3;栈顶 5 小于 7,弹出 5;栈为空,入栈 7
  • [7,1] 栈顶 7 大于 1, 入栈 1

对于单调 递增 栈,当 从左到右 遍历进行入栈时,单调递增栈的序列表示的 是, 左边第一个大于等于入栈元素的数

从右往左 入栈时,单调递增栈序列表示的是, 右边第一个大于等于入 栈元素的数

而单调 递减 栈则可以用来找 第一个比入栈元素小的数

有的问题,还需要限制 严格递增或者严格递减 ,即栈序列都是严格递增递减 的,不会出现相等的元素, 例如739. 每日温度

巧记

  • 要寻找 更小值 ,那么就要形成变 “小” 的单调栈,所以选择 单调递减栈 ,如果要找 左边 第一个更小值,就从 左边 开始遍历
  • 要寻找 更大值 ,那么就要形成变 “大” 的单调栈,所以选择 单调递增栈 ,如果要找 左边 第一个更大值,就从 左边 开始遍历

练习题

Refs

Author: Spike Leung

Date: 2022-08-22 Mon 00:00

License: CC BY-NC 4.0