单调栈与栈的区别是什么？

单调栈是一种特殊类型的栈结构，顾名思义就是栈内元素单调按照递增(或递减)顺序排列的栈。

单调栈是一种特殊类型的栈结构，顾名思义就是栈内元素单调按照递增(或递减)顺序排列的栈。

单调栈主要用于以时间复杂度 O(n)来解决 NGE(Next Greater Element)问题，通俗的说就是解决类似`找出第一个大于 X 或者第一个小于 X 的元素`的问题。

举个例子，假设用[a,b,c] 表示一个栈。 最左侧元素 a 为栈底元素，最右侧 c 为栈顶元素。

那么：

[1,2,3,4] 是一个单调递增栈;

[3,2,1] 是一个单调递减栈;

[1,3,2] 不是一个合法的单调栈。

举个例子：需要将数组 [1,3,4,5,2,9,6] 压入单调栈。

* 依次将递增序列 1，3，4，5 压入单调栈，此时的栈为：[1,3,4,5]

* 如果继续压入 2，此时的栈为：[1,3,4,5,2] 违反了单调递增栈的规定。因此执行 pop 操作，直至剩下的栈内元素，当 2 入栈时仍然能够满足单调递增。

* 因此栈内元素只剩 1：[1]. 压入 2，此时的栈为：[1,2]. 继续压入 9，此时的栈为：[1,2,9]

* 如果继续压入 6，则不满足单调递增栈的特性, 因此让 9 出栈，然后压入 6：[1,2,6]