N个整数组成的数组，定义子数组a[i]…a[j]的宽度为：max(a[i]…a[j]) - min(a[i]…a[j])，求所有子数组的宽度和。
第1行：1个数N，表示数组的长度。(1 <= N <= 50000) 第2 - N + 1行：每行1个数，表示数组中的元素(1 <= A[i] <= 50000)
输出所有子数组的宽度和。
5 1 2 3 4 5
20
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)的。 用两次单调栈一次确定该数作为区间最大值的使用区间，一次确定该数作为区间最小值的使用区间。
#include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> #include<math.h> #include<stack> #include<set> #include<queue> using namespace std; typedef long long LL; typedef struct node { int x; int id; } ss; LL ans[60000]; // 当前数作为最大的数左右范围 int ll[60000]; int rr[60000]; stack<ss> stcx; int main() { int n, m; while (scanf("%d", &n) != EOF) { int i, j; LL sum = 0; for (i = 1; i <= n; i++) { scanf("%lld", &ans[i]); } while (!stcx.empty()) { stcx.pop(); } for (i = 1; i <= n; i++) { while (!stcx.empty()) { ss ad = stcx.top(); if (ad.x >= ans[i]) { ss ak; ll[i] = ad.id + 1; ak.id = i; ak.x = ans[i]; stcx.push(ak); break; } else { stcx.pop(); rr[ad.id] = i - 1; } } if (stcx.empty()) { ll[i] = 1; ss ak; ak.x = ans[i]; ak.id = i; stcx.push(ak); } } while (!stcx.empty()) { ss ak = stcx.top(); stcx.pop(); rr[ak.id] = n; } for (i = 1; i <= n; i++) { sum += ans[i] * ((rr[i] - i + 1) * (i - ll[i] + 1)); } for (i = 1; i <= n; i++) { while (!stcx.empty()) { ss ad = stcx.top(); // 修改此处条件，求左区间 if (ad.x <= ans[i]) { ss ak; ll[i] = ad.id + 1; ak.id = i; ak.x = ans[i]; stcx.push(ak); break; } else { stcx.pop(); rr[ad.id] = i - 1; } } if (stcx.empty()) { ll[i] = 1; ss ak; ak.x = ans[i]; ak.id = i; stcx.push(ak); } } while (!stcx.empty()) { ss ak = stcx.top(); stcx.pop(); rr[ak.id] = n; } for (i = 1; i <= n; i++) { sum -= ans[i] * ((rr[i] - i + 1) * (i - ll[i] + 1)); } printf("%lld\n", sum); } return 0; }