首页 > 代码库 > 1215 数组的宽度
1215 数组的宽度
1215 数组的宽度
题目来源： Javaman
基准时间限制：1 秒 空间限制：131072 KB 分值: 80
收藏
关注N个整数组成的数组，定义子数组a[i]..a[j]的宽度为：max(a[i]..a[j]) - min(a[i]..a[j])，求所有子数组的宽度和。
Input
第1行：1个数N，表示数组的长度。(1 <= N <= 50000)第2 - N + 1行：每行1个数，表示数组中的元素(1 <= A[i] <= 50000)
Output
输出所有子数组的宽度和。
Input示例
512345
Output示例
20
思路：单调栈；
我们只要统计每个数做为最小的数和最大的数所在区间有多少个。这样求当前数作为最大的数左右范围，这个用单调栈维护下，同理最小的也是
然后左区间大小乘右区间大小就是这个数作为最大的出现的区间数；
以1 5 4 2 3为例，逐个入栈计算每个数的右边界：
1入栈 => 1
5入栈，前面所有比5小的出栈，并将右边界设为5 => 5 (确定了1的右边界是5，对应下标为1)
4入栈，前面所有比4小的出栈，并将右边界设为4 => 5 4
2入栈，前面所有比2小的出栈，并将右边界设为2 => 5 4 2
3入栈，前面所有比3小的出栈，并将右边界设为3 => 5 4 3(确定了2的右边界是3，对应下标为4)
最后所有数出栈，将5 4 3这3个数的右边界的下标设为5。
这样可以确认，每个数字最多进一次栈出一次栈，所有复杂度是O(n)的。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<math.h> 6 #include<stack> 7 #include<set> 8 #include<queue> 9 using namespace std; 10 typedef long long LL; 11 typedef struct node 12 { 13 int x; 14 int id; 15 } ss; 16 LL ans[60000]; 17 int ll[60000]; 18 int rr[60000]; 19 stack<ss>stcx; 20 int main(void) 21 { 22 int n,m; 23 while(scanf("%d",&n)!=EOF) 24 { 25 int i,j; 26 LL sum = 0; 27 for(i = 1; i <= n; i++) 28 { 29 scanf("%lld",&ans[i]); 30 } 31 while(!stcx.empty()) 32 stcx.pop(); 33 for(i = 1; i <= n; i++) 34 { 35 while(!stcx.empty()) 36 { 37 ss ad = stcx.top(); 38 if(ad.x >= ans[i]) 39 { 40 ss ak; 41 ll[i] = ad.id+1; 42 ak.id = i; 43 ak.x = ans[i]; 44 stcx.push(ak); 45 break; 46 } 47 else 48 { 49 stcx.pop(); 50 rr[ad.id] = i-1; 51 } 52 } 53 if(stcx.empty()) 54 { 55 ll[i] = 1; 56 ss ak; 57 ak.x = ans[i]; 58 ak.id = i; 59 stcx.push(ak); 60 } 61 } 62 while(!stcx.empty()) 63 { 64 ss ak = stcx.top(); 65 stcx.pop(); 66 rr[ak.id] = n; 67 //printf("1\n"); 68 } 69 70 for(i = 1; i <= n; i++) 71 { 72 sum+=ans[i]*((rr[i]-i+1)*(i-ll[i]+1)); 73 } 74 for(i = 1; i <= n; i++) 75 { 76 while(!stcx.empty()) 77 { 78 ss ad = stcx.top(); 79 if(ad.x <= ans[i]) 80 { 81 ss ak; 82 ll[i] = ad.id+1; 83 ak.id = i; 84 ak.x = ans[i]; 85 stcx.push(ak); 86 break; 87 } 88 else 89 { 90 stcx.pop(); 91 rr[ad.id] = i-1; 92 } 93 } 94 if(stcx.empty()) 95 { 96 ll[i] = 1; 97 ss ak; 98 ak.x = ans[i]; 99 ak.id = i;100 stcx.push(ak);101 }102 }103 while(!stcx.empty())104 {105 ss ak = stcx.top();106 stcx.pop();107 rr[ak.id] = n;108 }109 for(i = 1; i <= n; i++)110 {111 sum-=ans[i]*((rr[i]-i+1)*(i-ll[i]+1));112 }113 printf("%lld\n",sum);114 }115 return 0;116 }
1215 数组的宽度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。