制作网站基本步骤,美食网站开发毕业设计的主要内容,中山网站seo优化,品牌建设不目录 1.单调栈
例题#xff1a;【模板】单调栈
例题:求和
2.单调队列 例题#xff1a;滑动窗口 1.单调栈
例题#xff1a;【模板】单调栈
可以想象出一个柱状图#xff0c;值越大#xff0c;这个柱子越高
以此题的样例为例#xff1a;
第一个数为7#xff0c;想…目录 1.单调栈
例题【模板】单调栈
例题:求和
2.单调队列 例题滑动窗口 1.单调栈
例题【模板】单调栈
可以想象出一个柱状图值越大这个柱子越高
以此题的样例为例
第一个数为7想象一个高度为7的柱子它的左边没有任何数所以直接输出-1
然后第二个数为8想象高度为8的柱子从右往左靠近7因为7比8小所以输出7
第三个数为55从右往左靠近8而5比8小所以8被删除7大于5所以7也被删除
此时5左边就没数了输出-1
第四个数为6大于5所以输出5
第五个数为7大于6所以输出6 用栈的方法
#includebits/stdc.h
using namespace std;
using ll long long;
const int N 2e5 10;int a[N],l[N];int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);stackint stk;int n;cin n;for(int i 1; i n; i) cin a[i];for(int i 1; i n; i){while(stk.size() stk.top() a[i]) stk.pop();if(stk.empty()) l[i] -1;else l[i] stk.top();stk.push(a[i]);}for(int i 1; i n; i)cout l[i] ;return 0;
}
例题:求和
这题要对一个数的左边和右边都进行单调栈求比它小的值 #includebits/stdc.h
using namespace std;
using ll long long;
const int N 1e5 10;ll a[N],l[N],r[N];
int stk[N];
int top;//表示栈中元素个数int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n;cin n;for(int i 1; i n; i) cin a[i];for(int i 1; i n; i){while(top a[i] a[stk[top]]) top--;if(top ! 0) l[i] stk[top];else l[i] 0;stk[top] i;}top 0;//清空栈for(int i n; i 1; i--){while(top a[i] a[stk[top]]) top--;if(top ! 0) r[i] stk[top];else r[i] n 1;stk[top] i;}ll ans 0;for(int i 1; i n; i) ans a[i] * (r[i] - i) * (i - l[i]);cout ans;return 0;
} 2.单调队列 例题滑动窗口
以求窗口内最大值为例想象一个双端队列从右边入队每次入队与原来的队列中的最右边的元素比较大小如果它的数值更大那么就从右边pop掉原来队列中最右端的那个数直到最左边的元素最大为止 #includebits/stdc.h
using namespace std;
using ll long long;
const int N 2e5 10;int a[N];int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,k;cin n k;for(int i 1; i n; i) cin a[i];dequeint dq;//求最大值for(int i 1; i n; i){while(dq.size() k i - dq.front()) dq.pop_front();while(dq.size() a[dq.back()] a[i]) dq.pop_back();dq.push_back(i);if(i k) cout a[dq.front()] ;}dq.clear();cout endl;//求最小值for(int i 1; i n; i){//区间合法while(dq.size() k i - dq.front()) dq.pop_front();while(dq.size() a[dq.back()] a[i]) dq.pop_back();dq.push_back(i);if(i k)cout a[dq.front()] ;}return 0;
}
