浅谈单调栈

单调栈，顾名思义，具有单调性的栈。

• 单调，指满足一个序列是一个从小到大的序列或从大到小的序列。

• 栈（\(stack\)）是以一种线性存储结构，它具有以下特点：栈中的数据元素遵守“先进后出（\(First\ in\ Last\ out\)）”的原则，简称 FILO 结构；限定只能在栈顶进行插入和删除操作。

所以，何为单调栈，我们只需要维护一个具有单调性的栈。

如何维护一个具有单调性的栈，我们以单调递增栈为例。

• 将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

• 我们来模拟一下单调栈的过程。

• 例如，现在栈中自底向顶的序列为 \(\{0,2,5,10,32\}\)。

  • 现在，我们需要将 \(3\) 加入栈中。
    • 我们比较 \(0\) 和 \(3\) 的大小，发现 \(0<3\)，所以将 \(0\) 弹出栈。
    • 我们接着比较 \(2\) 和 \(3\) 的大小，发现 \(2<3\)，所以将 \(2\) 弹出栈。
    • 我们接着比较 \(5\) 和 \(3\) 的大小，发现 \(5>3\)，所以 \(3\) 进入栈。比较结束。
    • 此时栈中自底向顶的序列为 \(\{3,5,10,32\}\)。
  • 接着，我们需要将 \(20\) 加入栈中。
    • 我们比较 \(20\) 和 \(3\) 的大小，发现 \(3<20\)，所以将 \(3\) 弹出栈。
    • 我们接着比较 \(20\) 和 \(5\) 的大小，发现 \(5<20\)，所以将 \(5\) 弹出栈。
    • 我们接着比较 \(20\) 和 \(32\) 的大小，发现 \(32>20\)，所以 \(20\) 进入栈。比较结束。
    • 此时栈中自底向顶的序列为 \(\{20,32\}\)。