react可以做门户网站么,网站怎么做抽奖,重庆市建设工程安全管理协会,织梦 商城网站题目来源
力扣2865美丽塔I
题目概述
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i #xff0c;高度为 heights[i] 。
如果以下条件满足#xff0c;我们称这些塔是 美丽 的#xff1a;
1 heights…题目来源
力扣2865美丽塔I
题目概述
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i 高度为 heights[i] 。
如果以下条件满足我们称这些塔是 美丽 的
1 heights[i] maxHeights[i] heights 是一个 山脉 数组。
解题思路
思路一遍历一遍数组假设每个位置为顶峰分别计算该位置为顶峰时的山脉高度并记录最大值 思路二使用两个数组栈或者双端队列都行最好是栈方便编码一个记录从左到右递增序列在某个位置的最大高度和另一个记录从右到左递增序列在某个位置的最大高度和同一个位置的最大高度和相加就是该位置为顶峰的结果。
代码实现
java实现
public class Solution {public long maximumSumOfHeights(ListInteger maxHeights) {// 长度int length maxHeights.size();// 构造一座从左到右逐渐增高的山脉数组int[] rightMaxMountain new int[length];rightMaxMountain[0] maxHeights.get(0);// 表示记某个位置为顶峰,从左递增山脉的累计高度long[] rightMaxMountainHeightSum new long[length];rightMaxMountainHeightSum[0] rightMaxMountain[0];// 表示已构造山脉长度for (int i 1; i length; i) {// 当前高度int current maxHeights.get(i);long temp rightMaxMountainHeightSum[i - 1];// 如果当前高度比已经构造的山高度低已构造高的部分销毁int tempCount i ;while (tempCount ! 0 rightMaxMountain[tempCount - 1] current) {temp - (rightMaxMountain[tempCount - 1] - current);rightMaxMountain[tempCount - 1] current;tempCount--;}// 记录最大高度rightMaxMountainHeightSum[i] temp (rightMaxMountain[i] current);}// 构造一座从右到左逐渐增高的山脉数组int[] leftMaxMountain new int[length];leftMaxMountain[length - 1] maxHeights.get(length - 1);// 表示记某个位置为顶峰,从右递增山脉的累计高度long[] leftMaxMountainHeightSum new long[length];leftMaxMountainHeightSum[length - 1] leftMaxMountain[length - 1];// 结果long result rightMaxMountainHeightSum[length - 1] leftMaxMountainHeightSum[length - 1] - maxHeights.get(length - 1);for (int i length - 2; i 0; i--) {// 当前高度int current maxHeights.get(i);long temp leftMaxMountainHeightSum[i 1];// 如果已构造山脉比当前高度高销毁已构造高的部分int tempCount i;while (tempCount ! length - 1 current leftMaxMountain[tempCount 1]){temp - (leftMaxMountain[tempCount 1] - current);leftMaxMountain[tempCount 1] current;tempCount;}// 记录最大高度leftMaxMountainHeightSum[i] temp (leftMaxMountain[i] current);result Math.max(result, leftMaxMountainHeightSum[i] rightMaxMountainHeightSum[i] - current);}return result;}
}c实现
class Solution {
public:long long maximumSumOfHeights(vectorint maxHeights) {// 长度int length maxHeights.size();// 构造一座从左到右逐渐增高的山脉数组int* rightMaxMountain new int[length];rightMaxMountain[0] maxHeights[0];// 表示记某个位置为顶峰,从左递增山脉的累计高度long long* rightMaxMountainHeightSum new long long[length];rightMaxMountainHeightSum[0] rightMaxMountain[0];// 表示已构造山脉长度for (int i 1; i length; i) {// 当前高度int current maxHeights[i];long temp rightMaxMountainHeightSum[i - 1];// 如果当前高度比已经构造的山高度低已构造高的部分销毁int tempCount i;while (tempCount ! 0 rightMaxMountain[tempCount - 1] current) {temp - (rightMaxMountain[tempCount - 1] - current);rightMaxMountain[tempCount - 1] current;tempCount--;}// 记录最大高度rightMaxMountainHeightSum[i] temp (rightMaxMountain[i] current);}// 构造一座从右到左逐渐增高的山脉数组int* leftMaxMountain new int[length];leftMaxMountain[length - 1] maxHeights[length - 1];// 表示记某个位置为顶峰,从右递增山脉的累计高度long long* leftMaxMountainHeightSum new long long[length];leftMaxMountainHeightSum[length - 1] leftMaxMountain[length - 1];// 结果long long result rightMaxMountainHeightSum[length - 1] leftMaxMountainHeightSum[length - 1] - maxHeights[length - 1];for (int i length - 2; i 0; i--) {// 当前高度int current maxHeights[i];long temp leftMaxMountainHeightSum[i 1];// 如果已构造山脉比当前高度高销毁已构造高的部分int tempCount i;while (tempCount ! length - 1 current leftMaxMountain[tempCount 1]) {temp - (leftMaxMountain[tempCount 1] - current);leftMaxMountain[tempCount 1] current;tempCount;}// 记录最大高度leftMaxMountainHeightSum[i] temp (leftMaxMountain[i] current);long long newResult leftMaxMountainHeightSum[i] rightMaxMountainHeightSum[i] - current;result result newResult ? result : newResult;}return result;}
};算法题记录
