单调栈（C/C++）-慈云数据

引言：

单调队列和单调栈都是一种数据结构，应用十分广泛，在蓝桥杯、ICPC、CCPC等著名编程赛事都是重点的算法，今天博主将自己对单调栈与单调队列的理解以及刷题的经验，用一篇博客分享给大家，希望对大家有所帮助，它们用于解决类似“寻找最大值与最小值”这样的问题。它们的区别在于如何维护数据的单调性。、

单调栈（Monotonic Stack）：
- 单调栈是一种栈数据结构，只能在栈顶进行插入和删除操作。
- 单调栈的特点是栈中的元素按照一定的单调性排列，常用的有单调递增和单调递减。
- 在插入新元素时，如果新元素破坏了当前的单调性，则从栈顶删除一部分元素，直到满足单调性要求。这样可以保证栈中的元素保持单调性。
- 单调栈的典型应用是在寻找下一个更大/更小元素的问题。
单调队列（Monotonic Queue）：
- 单调队列是一个双端队列，支持在队列两端进行插入和删除操作。
- 单调队列的特点是队列中的元素按照一定的单调性排列，常用的有单调递增和单调递减。
- 在插入新元素时，如果新元素破坏了当前的单调性，则在队尾删除一部分元素，直到满足单调性要求。这样可以保证队列中的元素保持单调性。
- 单调队列的典型应用是在滑动窗口中寻找最大/最小值的问题。

单调队列和单调栈都是用于维护数据的单调性，但单调队列是双端队列，用于在滑动窗口中寻找最大/最小值，而单调栈是栈数据结构，用于寻找下一个更大/更小元素。

下面我们对单调栈进行深度解析

单调栈：

单调栈是一种数据结构，通常用于解决一些与序列相关的问题，特别是在需要找到元素在序列中的「下一个更大元素」或「下一个更小元素」的情况下。单调栈可以用于在线性时间复杂度内解决这些问题。

单调栈分为单调递增栈和单调递减栈两种类型：

1.单调递增栈：

栈中元素从栈底到栈顶递增。在处理序列时，当遇到一个元素时，如果该元素比栈顶元素大，就可以将栈顶元素出栈，直到栈为空或者栈顶元素大于等于当前元素。这样，栈中的元素就是在当前元素之前且比当前元素小的元素。

2.单调递减栈：

栈中元素从栈底到栈顶递减。在处理序列时，当遇到一个元素时，如果该元素比栈顶元素小，就可以将栈顶元素出栈，直到栈为空或者栈顶元素小于等于当前元素。这样，栈中的元素就是在当前元素之前且比当前元素大的元素。

使用单调栈的一般步骤如下：

1.创建一个空栈。

2.遍历待处理的序列，对于每个元素执行以下操作：

1.如果当前元素比栈顶元素大（或小，取决于是递增栈还是递减栈），则持续将栈顶元素出栈，直到栈为空或者栈顶元素满足某种条件（例如比当前元素大或小）。

2.记录弹出的元素，说明他是单调递减栈或单调递增栈第一个不满足的元素，可以在此元素根据题意进行操作

3.如果栈不为空，比较当前元素与栈顶元素的大小：

4..将当前元素入栈。

单调栈常用于解决一些数组或序列相关的问题，如找到下一个更大元素、下一个更小元素。

模板奉上：

第一种使用stack

stack st; // 单调栈，存储元素的下标
nums[n]=-1; //多加一个-1元素，防止到最后栈中还是单调递增栈，未能更新最大值
//单调递减栈就是nums[n]=0x3f3f3f;
    for (int i = 0; i n;
    for(int i=1;i>a[i];
    }
    for(int i=n;i>=1;i--){
        while(!stk.empty()&&a[stk.top()]

单调栈（C/C++）

引言：

单调栈（Monotonic Stack）：

单调队列（Monotonic Queue）：