目录链接：
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目：
https://github.com/September26/java-algorithms
原题链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
描述：
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
如果以下条件满足，我们称这些塔是 美丽 的：
1 <= heights[i] <= maxHeights[i]-
heights是一个 山脉 数组。
如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组：
- 对于所有
0 < j <= i，都有heights[j - 1] <= heights[j] - 对于所有
i <= k < n - 1，都有heights[k + 1] <= heights[k]
请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
示例 1：
输入：maxHeights = [5,3,4,1,1] 输出：13 解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为： - 1 <= heights[i] <= maxHeights[i] - heights 是个山脉数组，峰值在 i = 0 处。 13 是所有美丽塔方案中的最大高度和。
示例 2：
输入：maxHeights = [6,5,3,9,2,7] 输出：22 解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为： - 1 <= heights[i] <= maxHeights[i] - heights 是个山脉数组，峰值在 i = 3 处。 22 是所有美丽塔方案中的最大高度和。
示例 3：
输入：maxHeights = [3,2,5,5,2,3] 输出：18 解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为： - 1 <= heights[i] <= maxHeights[i] - heights 是个山脉数组，最大值在 i = 2 处。 注意，在这个方案中，i = 3 也是一个峰值。 18 是所有美丽塔方案中的最大高度和。
提示：
1 <= n == maxHeights <= 1031 <= maxHeights[i] <= 109
解题思路：
这题适用于单调栈的解题思路。
构建两个数组dpLeft和dpRight。dpLeft[i]代表i的左侧从左向右单调非递减，并且使0到i位置之和最大的值。dpRight[i]代表i的右侧从左向右单调非递增，并且使i到n-1位置之和最大的值。
求dpRight[i]的时候，我们从右向左遍历，构造单调递减的栈。如果i位置的值小于栈顶，则我们出栈，直到栈为空。
使用同样方式求出dpLeft。某个位置i的大高度dp[i] = dpLeft[i] + dpRight[i] - maxHeights.get(i);文章来源：https://www.toymoban.com/news/detail-822913.html
我们求出最大的dp[i]即可。文章来源地址https://www.toymoban.com/news/detail-822913.html
代码：
public class Solution2865 {
public long maximumSumOfHeights(List<Integer> maxHeights) {
Stack<Node> stack = new Stack<>();
long[] dpRight = new long[maxHeights.size()];
for (int i = maxHeights.size() - 1; i >= 0; i--) {
Node node = computeNode(maxHeights, i, stack, maxHeights.size());
dpRight[i] = node.sum;
}
stack.clear();
long maxSum = 0;
for (int i = 0; i < maxHeights.size(); i++) {
Node node = computeNode(maxHeights, i, stack, -1);
long sum = node.sum + dpRight[i] - maxHeights.get(i);
maxSum = Math.max(sum, maxSum);
}
return maxSum;
}
private Node computeNode(List<Integer> maxHeights, int i, Stack<Node> stack, int defaultIndex) {
long value = maxHeights.get(i);
while (stack.size() > 0 && value < stack.peek().value) {
stack.pop();
}
long rightSum = 0;
long rightIndex = defaultIndex;
long rightValue;
Node node;
if (stack.size() > 0) {
node = stack.peek();
rightSum = node.sum;
rightIndex = node.index;
rightValue = node.value;
if (value == rightValue) {
node.updateIndex(i);
return node;
}
}
node = new Node(i, value);
node.sum = Math.abs(rightIndex - i) * value + rightSum;
stack.add(node);
return node;
}
static class Node {
long value;
int index;
long sum;
Node(int index, long value) {
this.index = index;
this.value = value;
}
public void updateIndex(int index) {
this.sum += Math.abs(this.index - index) * this.value;
this.index = index;
}
}
}到了这里，关于LeetCode解法汇总2865. 美丽塔 I的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
