【力扣每日一题】力扣2865美丽塔I

题目来源

力扣2865美丽塔I

题目概述

给你一个长度为?n?下标从?0?开始的整数数组?maxHeights?。

你的任务是在坐标轴上建?n?座塔。第?i?座塔的下标为?i?，高度为?heights[i]?。

如果以下条件满足，我们称这些塔是 美丽 的：

1 <= heights[i] <= maxHeights[i]?heights?是一个?山脉?数组。

解题思路

思路一：遍历一遍数组，假设每个位置为顶峰，分别计算该位置为顶峰时的山脉高度，并记录最大值； 思路二：使用两个数组（栈或者双端队列都行，最好是栈，方便编码）一个记录从左到右递增序列在某个位置的最大高度和，另一个记录从右到左递增序列在某个位置的最大高度和，同一个位置的最大高度和相加就是该位置为顶峰的结果。

代码实现

java实现

public class Solution {
    public long maximumSumOfHeights(List<Integer> 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(vector<int>& 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;
    }
};

算法题记录