本文主要是介绍2866.美丽塔 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源：
leetcode题目，网址：2866. 美丽塔 II - 力扣（LeetCode）
解题思路：
单调栈+dp。维护两个数组 pre 和 suffix，pre[i] 表示以第 i 个为山峰时 [0,i] 的最大值，suffix[i]表示以 第 i 个为山峰时 [i,n-1] 的最大值。pre[i]+suffix[i]-maxHeights[i] 的最大值即为所求。
解题代码：
class Solution {
public:long long maximumSumOfHeights(vector<int>& maxHeights) {vector<long long> pre=getPreVector(maxHeights);vector<long long> suffix=getSuffixVector(maxHeights);long long res=0;for(int i=0;i<maxHeights.size();i++){res=max(pre[i]+suffix[i]-maxHeights[i],res);}return res;}vector<long long> getSuffixVector(vector<int>& maxHeights){int n=maxHeights.size();vector<long long> res(n);stack<int> stack1;for(int i=n-1;i>=0;i--){while(!stack1.empty()&& maxHeights[i]<maxHeights[stack1.top()]){stack1.pop();}if(stack1.empty()){res[i]=(long long)(n-i)*(maxHeights[i]);}else{int j=stack1.top();res[i]=(long long)(j-i)*maxHeights[i]+res[j];}stack1.push(i);}return res;}vector<long long> getPreVector(vector<int>& maxHeights){vector<long long> res;stack<int> stack1;for(int i=0;i<maxHeights.size();i++){while(!stack1.empty() && maxHeights[i]<maxHeights[stack1.top()]){stack1.pop();}if(stack1.empty()){res.push_back((i+1)*(long long)maxHeights[i]);}else{int j=stack1.top();res.push_back((i-j)*(long long)maxHeights[i]+res[j]);}stack1.push(i);}return res;}
};总结：
没想出来，看官方题解的。
这篇关于2866.美丽塔 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
