题意：求数组中每个连续子序列的的最大值-最小值之和。
思路：题意可以理解为加上每一个序列的最大值，减去每一个序列的最小值。每个数都可以作为某一连续子序列的最大值和最小值，所以可以枚举每一个数作为最值的区间，暴力枚举时间复杂度过高，所以利用单调栈找出每个数左边或右边第一个比本身小的数，这样该数就是区间中最小的数。同理也可以找该数为最大数的区间。这里有个坑就是有可能答案会算重复。比如1 4 1，第一个1最为最小值的时候会算一个1 4 1，第三个1最为最小值的时候也会算一个1 4 1。只有我们用单调栈来求L【i】的时候保持左开右闭就可以保证只算一次。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
int a[N],l[N],r[N];
stack<int> s;
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int n;
long long ans = 0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
while(!s.empty()&&a[s.top()]>a[i]) s.pop();
if(s.empty()) l[i] = 1;
else l[i] = s.top() + 1;
s.push(i);
}
while(!s.empty())
s.pop();
for(int i=n;i>=1;i--){
while(!s.empty()&&a[s.top()]>=a[i]) s.pop();
if(s.empty()) r[i] = n;
else r[i] = s.top() - 1;
s.push(i);
}
while(!s.empty())
s.pop();
for(int i=1;i<=n;i++)
ans -= 1LL * (i - l[i] + 1) * (r[i] - i + 1) * a[i];
for(int i=1;i<=n;i++){
while(!s.empty()&&a[s.top()]<a[i]) s.pop();
if(s.empty()) l[i] = 1;
else l[i] = s.top() + 1;
s.push(i);
}
while(!s.empty())
s.pop();
for(int i=n;i>=1;i--){
while(!s.empty()&&a[s.top()]<=a[i]) s.pop();
if(s.empty()) r[i] = n;
else r[i] = s.top() - 1;
s.push(i);
}
for(int i=1;i<=n;i++)
ans += 1LL * (i - l[i] + 1) * (r[i] - i + 1) * a[i];
cout<<ans<<'\n';
return 0;
}