在满足"先进后出"特性的基础上,若栈中元素从栈顶到栈底具有单调性,则称其为单调栈。

构造单调递增栈的过程概括如下:从左向右依次遍历序列,处理每一个元素。若栈为空,则直接将当前元素入栈;若栈非空,判断栈顶位置与对应的元素是否小于或等于当前元素,将小于或等于当前元素的栈顶元素依次出栈,知道栈为空或栈顶位置与对应的元素大于当前元素,再将当前元素入栈。

由此可知,构造过程中元素的进栈操作需根据情况弹出单调栈中既有元素,但整个过程中每个元素入栈只有一次,出栈一次,所以其时间复杂度不再是普通的常数时间,而是一个与序列长度成正比的线性时间。

主要解决问题类型:

  1. 查找左、右区间中第一个比当前元素大或小的元素。
  2. 确定元素是否某个区间最值
  3. 求最大区间
  4. 求柱状图中的最大矩形

例题：

  1. 模板题
  2. 柱状图
  3. 接雨水
  4. 给定一个非负整数num和一个整数k,请移除num中的k位数字,使得剩下的数最小。注:num只包含数字,且除了0以外不包含任何前导0