单调栈是一种栈的特殊形态,要求每次入栈的元素必须要有序。如果新元素入栈不符合要求,则将之前的元素出栈,直到符合要求再将新元素入栈。

单调栈可分为单调递增栈和单调递减栈:

  • 单调递增栈:只有比栈顶小的元素才能入栈;
  • 单调递减栈:只有比栈顶大的元素才能入栈。

适用场景

一般用于解决求第一个大于xxx或第一个小于xxx元素的问题。