单调栈

· · 个人记录

基础概念

定义

栈内的元素，按照某种方式排序下，如果新入栈的元素破坏了单调性，就弹出栈内元素直到满足单调性。

作用

可以方便地求出一个数的左边或右边第一个比它大或小的数，总体时间复杂度是 O(n) 。

原理

单调栈是一种动态的数据结构。

假如有一串数 { 3 ， 1 ， 4 ， 3 } ，求左边第一个大于它的数。

然鹅，这里的 1 其实是没用的，为什么呢？

假设要新加一个数 x ，则有两种情况：

因此不必再存储 x 。

那么我们可以得到一个具有单调性的序列，即 { 4 ， 3 }，之后每次查询只需从右往左弹出元素，直到满足条件。

还有一个性质：越早进入的数越晚弹出，即先入后退，可以想到栈。

而每个元素至多入栈一次、出栈一次，时间复杂度是线性的。

如何实现

流程

下面是一个单调递减栈的创建：

  1. 创建一个空栈 s 。
  2. 对于每个新的元素 x，若栈顶元素 < x ，则弹出栈顶元素。
  3. 重复 2 直到满足条件。
  4. 此时的栈顶即为左边第一个大于 x 的元素。
  5. 将 x 入栈。

    代码实现

    void stack_dd(int n) //严格单调递减
{
  for(int i=1; i<=n;i++)
  {
      while(!s.empty()&&a[i]>=a[s.top()])
      {
          s.pop();
      }
      cout<<(s.empty()?-1:s.top())<<endl;
      s.push(i);
  }
}