单调队列与单调栈＜2＞—

单调队列与单调栈＜2＞——单调栈

单调栈的定义

单调递增栈

栈中元素从栈底到栈顶是递增的。

单调递减栈

栈中元素从栈底到栈顶是递减的。

单调栈的核心内容

我们从左到右遍历元素，构造单调栈（从栈顶到栈底递增或减）：在 i 从左往右遍历的过程中，我们可以用一个单调栈来保存 i 左边的所有元素（不包括 i 指向的元素），i 遍历一个元素单调栈就放入一个元素，每一个元素都必须入栈一次，下标越大的元素越接近栈顶，下标越小的元素越接近栈底。

在每个新的元素入栈前从栈顶依次去除所有不合法的元素，因为这些元素会破坏单调性，直到栈顶小于或大于该入栈元素，此时元素可以入栈。

简单来说，就是在入栈时删掉不合法元素，保证栈的单调性。

单调栈的应用

寻找左边第一个比它小的数

例题

给定一个长度为 N 的数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

Sol

朴素算法的时间复杂度为 $\Theta(N^2)$ ，所以考虑优化。

在元素入栈前从栈顶依次去除所有不合法元素，因为这些元素会破坏单调性，直到栈顶小于该入栈元素，此时元素可以入栈，栈的单调性没被破坏，并且此时的栈顶就是要寻找的答案——左边第一个比它小的数。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>arr[i];for(int i=1;i<=n;i++){while(!stk.empty() && stk.top()>=arr[i])stk.pop();//把栈内不合法的元素出栈if(!stk.empty())ans[i]=stk.top();//栈顶就是答案elseans[i]=-1;stk.push(arr[i]);}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}

寻找左边第一个比它大的数

和上面的思路相同。改变符号即可。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>arr[i];for(int i=1;i<=n;i++){while(!stk.empty() && stk.top()<=arr[i])stk.pop();//把栈内不合法的元素出栈if(!stk.empty())ans[i]=stk.top();//栈顶就是答案elseans[i]=-1;stk.push(arr[i]);}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}

寻找左边第一个比它小的数的下标

Sol

很简单，我们让栈维护的是下标即可。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>arr[i];for(int i=1;i<=n;i++){while(!stk.empty() && arr[stk.top()]>=arr[i])stk.pop();//把栈内不合法的元素出栈if(!stk.empty())ans[i]=stk.top();//栈顶就是答案stk.push(i);}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}

寻找左边第一个比它大的数的下标

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>arr[i];for(int i=1;i<=n;i++){while(!stk.empty() && arr[stk.top()]<=arr[i])stk.pop();//把栈内不合法的元素出栈if(!stk.empty())ans[i]=stk.top();//栈顶就是答案stk.push(i);}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}

寻找右边第一个小于它的数

Sol

将数组倒序遍历即可。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>arr[i];for(int i=n;i>0;i--){while(!stk.empty() && stk.top()>=arr[i])stk.pop();//把栈内不合法的元素出栈if(!stk.empty())ans[i]=stk.top();//栈顶就是答案elseans[i]=-1;stk.push(arr[i]);}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}

寻找右边第一个大于它的数

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>arr[i];for(int i=n;i>0;i--){while(!stk.empty() && stk.top()<=arr[i])stk.pop();//把栈内不合法的元素出栈if(!stk.empty())ans[i]=stk.top();//栈顶就是答案elseans[i]=-1;stk.push(arr[i]);}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}

寻找右边第一个小于它的数的下标

例题:P5788

Sol

和之前的思路相同。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>arr[i];for(int i=n;i>0;i--){while(!stk.empty() && arr[stk.top()]>=arr[i])stk.pop();//把栈内不合法的元素出栈if(!stk.empty())ans[i]=stk.top();//栈顶就是答案stk.push(i);}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}

寻找右边第一个大于它的数的下标

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>arr[i];for(int i=n;i>0;i--){while(!stk.empty() && arr[stk.top()]<=arr[i])stk.pop();//把栈内不合法的元素出栈if(!stk.empty())ans[i]=stk.top();//栈顶就是答案stk.push(i);}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}