Problem:2866. 美丽塔 II

思路：分别用单调栈预算出每个峰顶的左右sum,然后枚举每个峰顶，最后取一个max。

Accode:

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int len = maxHeights.size();
        vector<long long> preSum(len),sufSum(len);
        stack<int> sta;
        long long sum = 0;
        for(int i=0;i<len;i++){
            while(sta.size() && maxHeights[sta.top()]>=maxHeights[i]){
                int right_idx = sta.top();
                sta.pop();
                if(sta.size()==0){
                    sum-=(long long)maxHeights[right_idx]*(right_idx+1);
                }
                else{
                    sum-=(long long)maxHeights[right_idx]*(right_idx-sta.top());
                }
            }
            if(sta.size()==0) sum+=(long long)(i+1)*maxHeights[i];
            else sum+=(long long )(i-sta.top())*maxHeights[i];
            sta.push(i);
            preSum[i] = sum;
        }
        sum = 0;
        while(sta.size()) sta.pop();
        for(int i=len-1;i>=0;i--){
            while(sta.size() && maxHeights[sta.top()]>=maxHeights[i]){
                int left_idx = sta.top();
                sta.pop();
                if(sta.size()==0){
                    sum-=(len-left_idx)*(long long)maxHeights[left_idx];
                }
                else {
                    sum-=(sta.top()-left_idx)*(long long)maxHeights[left_idx];
                }
            }
            if(sta.size())sum+=(sta.top()-i)*(long long)maxHeights[i];
            else sum+=(len-i)*(long long)maxHeights[i];
            sta.push(i);
            sufSum[i] = sum;
        }
        long long ans = 0;
        for(int i=0;i<len;i++){
            ans = max(ans,preSum[i]+sufSum[i]-maxHeights[i]);
        }
        return ans;

    }
};

时间复杂度：$o(n)$