单调栈

1.什么是单调栈？
从名字上就听的出来，单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈，故其分为两种
单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大

从上面的定义可以知道它就是一个栈，只不过里面存储的元素是有顺序的， 这里我们使用数组模拟栈：

#include<iostream>
#include<string>
using namespace std;
constexpr int N = 1e+5 + 10;
int st[N], tt, n;

// 这里的栈是满堆栈写法, 堆栈指针指向最后压入栈的有效数据项,此时堆栈入栈操作要先调整指针再写入数据,故这里是前置++

auto push(int x) { st[++tt] = x; }       // 入栈
auto pop() {--tt;}                       // 出栈
auto empty() -> bool { return tt == 0;}  // 判断是否为空, 初始值 tt = 0;表示为空
auto top() -> int { return st[tt]; }     // 返回栈顶元素

这里主要看单调栈的应用，因为其本身就是一个栈，在数据结构上没什么不一样的，关键是看其应用场景下如何实现元素的顺序存储.

相关练习链接 : 单调栈练习

#include<iostream>
using namespace std;

constexpr int N = 1e+5 + 10;
int st[N], tt, n;

auto push(int x) { st[++tt] = x; }       // 入栈
auto pop() {--tt;}                       // 出栈
auto empty() -> bool { return tt == 0;}  // 判断是否为空, 初始值 tt = 0;表示为空
auto top() -> int { return st[tt]; }     // 返回栈顶元素

auto main() -> int
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        int x; cin >> x;
        while(!empty() && top() >= x) pop();   // 先判断是否为空, 若不为空切栈顶元素大于等于目前比较的数， 则出栈栈顶元素，直到栈顶元素为符合条件
        if(!empty()) cout << top() << " ";
        else cout << "-1 "; 
        push(x);                              // 此时再插入x，x此时为栈顶，是栈顶最大的元素
    }
    cout << endl;
    return 0;
}

思路分析 : 例如这样一组数据 2 3 5 4 x 现在找x左边离它最近且比它小的那个数，首先第一个条件是离它最近，故这里考虑用一下朴素做法实现我们可以直接用栈，将前面的元素依次进栈，此时栈顶元素就是左边离它最近的元素，若该元素大于等于x，遍历下一个元素比较直到找到符合条件的数，在这里我们发现5这个数子无论如何都不会作为一个正解，因为其后面有个4， 故5永远都不会是一个可选的答案，故我们可以直接将这个数字直接出栈，而不用每次都遍历一遍。 这样每一个数字最多的操作就是入栈一次和出栈一次，时间复杂度为 O(n), 而朴素做法为O(n2);

单调栈的应用 – 优化最长上升子序列

练习链接:
最长上升子序列I
最长上升子序列II
Dp的做法

闫氏分析法 这里只用到一维 f[N] 就够了

                             | 集合 ： 结尾为数组下标为i的元素的上升子序列
                             |
  |-----------状态表示-------|
  |                          | 属性 :  max(集合中长度最长的子序列)
  | 
  | 
  |
  DP    
  |
  |
  |
  |
  |------------状态计算 :  首先本身就算一个长度， 故f[i] >= 1, 然后依次与a[1], a[2], ... , a[i - 1] 比较，若存在ai > ak, 则存在 f[i] = max(f[i], f[k] + 1) 这里+1为加上本身的长度

#include<iostream>
using namespace std;
constexpr int N = 1010;

int n, a[N], f[N];

auto main() -> int
{
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];

    int res =  -1;
    for(int i = 1; i <= n; ++i)
    {
        f[i] = 1;
        for(int j = 1; j < i; ++j)
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    cout << res << endl;

    return 0;
}

// 时间复杂度为 O(n2), 若N的数据为 10的6次方级别会超时, 

故这里用单调栈的思想进行优化, 注意这里是用到单调的思想并不是用一个栈来实现，准确地来说是一个单调数组,例如这样一组数据中 : 3 1 2 1 8 5 6 其中我们第一个数字和第二个数字作为长度为1的上升子序列，故其就是以第一个元素为开始和以第二个元素为开始且长度为上升子序列，且二者的长度均为1， 数据中的8均可以加入这个序列中，但显然加入数据为1的子序列中更好，因为它更小，故在长度为1的子序列中我们只需关注更小数结尾的就好了，故对于其他长度的子序列，我们只要保存其中结尾元素最小的那个子序列即可，这里我们是用一个数组，数组下标表示子序列长度，数组元素表示其结尾的那个数字。 这样处理之后其每一个长度所存储的值必然是严格单调递增。

优化后的代码

#include<iostream>
using namespace std;

constexpr int INF = 1e+9;
constexpr int N = 1e+5 + 10;

int n, a[N];       // 数组a[i]的含义为子序列长度为i, 且储存元素为长度为i的序列中结尾的最小值

auto main() -> int
{
    cin >> n;

    a[0] = -INF - 10;            // 子序列长度为0的结尾值直接设个最小值即可

    int t = 0;                   // 表示此时a数组所储存的最长子序列长度为t,初始为0
    for(int i = 1; i <= n; ++i)
    {
        int x; cin >> x;         // 依次输入待处理的数
        int l = 0, r = t;        // 这里用二分查找小于x的最大的那个数字
        while(r > l)
        {
            int mid = l + r + 1>> 1;
            if(a[mid] < x) l = mid;
            else r = mid - 1;
        }
        t = max(t, r + 1);       // 更新t
        a[++r] = x;              // 更新长度为r + 1长度的序列的结尾的值
    }
    cout << t << endl;           
    return 0;
}

单调队列

同样其本质就是队列的数据结构，只不过其存储的元素是有单调性的。队列使用数据模拟的代码如下:

constexpr int N = 1e+6 + 10;

int n,k;
int a[N], q[N], front, back;
auto push(int x) {q[back++] = x;}
auto pop() { ++front;}
auto empty() -> bool { return front == back; } 

与单调栈一样，主要还是看其应用，能否从一个问题中抽象出一个单调队列的模型，就可以用这个思想来优化算法，这里还是看例题 : 滑动窗口

思路分析

这道题目中， 如果按照朴素算法，即在一个大小为k的滑动窗口中依次比较k个数找到其中的最小值或者最小值， 但同样这里存在冗余的操作，例如在其中一个窗口中 3 6 1 中输出最小值， 6这个数字永远不会作为正解进行输出，因为其右边的1比6小，且其会在1之前先被滑出窗口，故这里并没有存储6的必要。 故这样的话这个窗口中所保存的数据一定是严格单调递增/递减的， 且队头元素即为此时窗口中的正解， 由于其窗口滑动的过程，窗口左边弹出元素，窗口右边进入元素，这一数据结构符合队列的特点，故这里就用队列来实现滑动窗口

#include<iostream>
using namespace std;

constexpr int N = 1e+6 + 10;

int n,k;
int a[N], q[N], front, back;                  // 此时q数组的队列存储的是下标
auto push(int x) {q[back++] = x;}
auto pop() { ++front;}
auto empty() -> bool { return front == back; } 

auto main() -> int
{
    cin >> n >> k;

    for(int i = 0; i < n; ++i) cin >> a[i];

    for(int i = 0; i < n; ++i)
    {
        if(!empty() && i - k + 1 > q[front]) pop();      // 判断此时队头的下标是否应该滑出
        while(!empty() && a[q[back - 1]] >= a[i]) --back;  // 若对尾元素大于x，从队尾出队， 因为要实现严格单调，且入队只能从队尾入
        push(i);
        if(i >= k - 1) cout << a[q[front]] << " ";
    }
    cout << endl;

    front = 0 , back = 0;
    for(int i = 0; i < n; ++i)
    {
        if(!empty() && i - k + 1 > q[front]) pop();
        while(!empty() && a[q[back - 1]] <= a[i]) --back;
        push(i);
        if(i >= k - 1) cout << a[q[front]] << " ";
    }

    return 0;
}