单调栈的定义
单调递增栈
- 栈中元素从栈底到栈顶是递增的。
单调递减栈
- 栈中元素从栈底到栈顶是递减的。
单调栈的核心内容
我们从左到右遍历元素，构造单调栈（从栈顶到栈底递增或减）：在 i 从左往右遍历的过程中，我们可以用一个单调栈来保存 i 左边的所有元素（不包括 i 指向的元素），i 遍历一个元素单调栈就放入一个元素，每一个元素都必须入栈一次，下标越大的元素越接近栈顶，下标越小的元素越接近栈底。
在每个新的元素入栈前从栈顶依次去除所有不合法的元素，因为这些元素会破坏单调性，直到栈顶小于或大于该入栈元素，此时元素可以入栈。
简单来说，就是在入栈时删掉不合法元素，保证栈的单调性。
单调栈的应用
寻找左边第一个比它小的数
例题
给定一个长度为 N 的数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
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() && 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;
}