莆田网站建设费用,数字logo创意设计,外国客户网站,深圳网站设计公司哪家专业目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 描述#xff1a;
给你一个长… 目录链接
力扣编程题-解法汇总_分享记录-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);
我们求出最大的dp[i]即可。 代码
public class Solution2865 {public long maximumSumOfHeights(ListInteger maxHeights) {StackNode 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(ListInteger maxHeights, int i, StackNode 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;}}
}
