2865. 美丽塔 I
思路：方法一，时间复杂度0(n^2)。枚举每一个点i作为当前山脉数组的最高点。然后我们通过预处理遍历其前面和后面，来更新两个数组f1、f2。
数组f1[i]：表示在满足非递减的情况下，区间0~i，以点i的高度heighs[i]为最高点所能形成的最大高度和。
数组f2[i]：表示在满足非递减的情况下，区间i~n-1，以点i的高度heighs[i]为最高点所能形成的最大高度和。
具体细节看注释。
class Solution {
public:
long long maximumSumOfHeights(vector<int>& heights) {
int n=heights.size();
vector<long long > f1(n,0),f2(n,0);
f1[0]=heights[0];
for(int i=1;i<heights.size();i++){
f1[i]+=heights[i];
for(int j=i-1;j>=0;j--){
//遇到前面的一个点j的heights[j]<=heights[i],那么直接就可以跳出
if(heights[j]<=heights[i]){
f1[i]+=f1[j];
break;
}else{
//没遇到之前，这些比heights[i]点高的高度都为heights[i]；
f1[i]+=heights[i];
}
}
}
f2[n-1]=heights[n-1];
for(int i=n-2;i>=0;i--){
f2[i]+=heights[i];
for(int j=i+1;j<n;j++){
//遇到后面的一个点j的heights[j]<=heights[i],那么直接就可以跳出
if(heights[j]<=heights[i]){
f2[i]+=f2[j];
break;
}else{
//没遇到之前，这些比heights[i]点高的高度都为heights[i]；
f2[i]+=heights[i];
}
}
}
long long mx=0;
for(int i=0;i<n;i++){
mx=max(mx,f1[i]+f2[i]-heights[i]);
}
return mx;
}
};
思路：方法二，时间复杂度0(n)。观察方法一会发现，在预处理时，我们每次都要再遍历一遍已遍历过的元素，只有当heights[j]<=heights[i]时才停下，那么我们直接维护一个非递减序列即可。细节看注释
class Solution {
public:
long long maximumSumOfHeights(vector<int>& heights) {
int n=heights.size();
vector<long long > f(n,0);
//维护一个非递减序列，记录的是下标
stack<int> st;
//哨兵，方便计算
st.push(n);
//保存到目前点i,所能形成的最大高度和
long long sum=0;
for(int i=n-1;i>=0;i--){
//栈中比点i还高的点，就需要从sum当中删掉，
while(st.size()>1&&heights[i]<heights[st.top()]){
int tmp=st.top();
st.pop();
//这个点的高度太高了，我们需要把区间[tmp,st.top()）的高度都减掉；
sum-=(long long)heights[tmp]*(st.top()-tmp);
}
//剔除比点i的高度heights[i]高的点后，需要将[i,st.top()）这段区间的高度都置为heights[i]
sum+=(long long)heights[i]*(st.top()-i);
f[i]=sum;
st.push(i);
}
st=stack<int>();
st.push(-1);
long long mx=0;
sum=0;
for(int i=0;i<n;i++){
while(st.size()>1&&heights[i]<heights[st.top()]){
int tmp=st.top();
st.pop();
sum-=(long long)heights[tmp]*(tmp-st.top());
}
sum+=(long long)heights[i]*(i-st.top());
mx=max(mx,sum+f[i]-heights[i]);
st.push(i);
}
return mx;
}
};