如何用ai给网站做logo,网站制作案例流程图,中国企业信息公示网登录官网,网站建设的工作在哪里找客户资源线性结构——单调栈①定义#xff1a;栈内的元素#xff0c;按照某种方式排序#xff08;单调递增或单调递减#xff09;如果新入栈的元素破坏了单调性#xff0c;就弹出栈内元素#xff0c;直到满足单调性②优点#xff1a;可以很方便地求出某个数左边或者右边第一个比… 线性结构——单调栈①定义栈内的元素按照某种方式排序单调递增或单调递减如果新入栈的元素破坏了单调性就弹出栈内元素直到满足单调性②优点可以很方便地求出某个数左边或者右边第一个比他大或者小的元素总时间复杂度为O(n)③如何维护单调栈以递增为例进栈操作每次入栈前先检验栈顶元素和进栈元素x的大小如果小于x就让x 直接入栈。如果栈顶元素大于等于x那么出栈直到栈空或者栈顶元素小于x。 【例1】最大矩形面积(poj2559) 1 #includebits/stdc.h2 using namespace std;3 const int N100002;4 int h[N],n;5 int line[N],L[N],R[N],top0;6 int main(){7 scanf(%d,n);8 for(int i1;in;i)9 scanf(%d,h[i]);
10 for(int i1;in;i){
11 while(toph[line[top]]h[i]) top--;
12 L[i]top?line[top]1:1;
13 line[top]i;
14 }
15 top0;
16 for(int in;i1;i--){
17 while(toph[line[top]]h[i]) top--;
18 R[i]top?line[top]-1:n;
19 line[top]i;
20 }
21 int maxn0;
22 for(int i1;in;i){
23 int ansh[i]*(R[i]-L[i]1);
24 maxnmax(maxn,ans);
25 }
26 coutmaxnendl;
27 return 0;
28 } 代码戳这里 【例2】玉蟾宫(luogu P4147) 题目传送门讲一讲我自己的思路(其实是同学教的)吧似乎不是很好的解但我感觉比较好理解……首先把输入的字符矩阵转移为数字即s[i][j]代表第i行第j列这一格上面连续的F的个数(如果这一格是S的话就是0)所以预处理之后就把样例变成了这样0 1 1 1 1 11 2 2 2 2 20 0 0 3 3 31 1 1 4 4 42 2 2 5 5 5代码实现 for(int i1;in;i)for(int j1;jm;j){char ch;cinch;if(chF) s[i][j]s[i-1][j]1;} 然后就有点类似于上面那道题了每一行分开分析找到每一个位置可以向左右扩展的最长的长度这是矩形的长而组成的矩形的宽就是这一格中对应的数字所以向左右两边扩展的条件就是要扩展的那一格中的数字一定大于等于当前扫描到的这一格的数字。(似乎没太讲清楚啊QAQ)每一行处理出一个可以组成的矩形的最大面积用一个maxn取最大值就可以找到最后的答案了。代码实现 for(int i1;in;i){int ans0;//用于记录当前这一行的矩形最大面积for(int j1;jm;j){int lj,rj;//l代表左边能扩展到的最远位置r代表右边能扩展到的最远位置while(l1s[i][l]s[i][j]) l--;l;while(rms[i][r]s[i][j]) r;r--;ansmax(ans,s[i][j]*(r-l1));//当前这一行的最大矩形面积}maxnmax(ans,maxn);//每一行的最大矩形面积比较取最大值
} 以下完整代码(没开O2的时候T了两个点QAQ) 1 // luogu-judger-enable-o22 #includecstdio3 #includecstring4 #includeiostream5 using namespace std;6 const int N1002;7 int K,n,m;8 int s[N][N];9 int maxn0;
10 int max(int x,int y){
11 return xy?x:y;
12 }
13 int main(){
14 //scanf(%d,K);
15 //while(K--){
16 memset(s,0,sizeof(s));
17 scanf(%d%d,n,m);
18 for(int i1;in;i)
19 for(int j1;jm;j){
20 char ch;
21 cinch;
22 if(chF) s[i][j]s[i-1][j]1;
23 }
24 for(int i1;in;i){
25 int ans0;//用于记录当前这一行的矩形最大面积
26 for(int j1;jm;j){
27 int lj,rj;//l代表左边能扩展到的最远位置r代表右边能扩展到的最远位置
28 while(l1s[i][l]s[i][j]) l--;
29 l;
30 while(rms[i][r]s[i][j]) r;
31 r--;
32 ansmax(ans,s[i][j]*(r-l1));//当前这一行的最大矩形面积
33 }
34 maxnmax(ans,maxn);//每一行的最大矩形面积比较取最大值
35 }
36 printf(%d\n,maxn*3);//最后别忘了乘3
37 //}
38 return 0;
39 } 代码戳这里 转载于:https://www.cnblogs.com/THWZF/p/10161208.html
