2866. 美丽塔 II --力扣 --JAVA

题目

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

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

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

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

如果存在下标?i?满足以下条件，那么我们称数组?heights?是一个?山脉?数组：

• 对于所有?0 < j <= i?，都有?heights[j - 1] <= heights[j]
• 对于所有?i <= k < n - 1?，都有?heights[k + 1] <= heights[k]

请你返回满足?美丽塔?要求的方案中，高度和的最大值?。

解题思路

1. 将列表转换成数组，方便读取数据；
2. 假设所有节点都可以作为最高峰：
   1. 当前节点小于下一节点则跳过当前节点直接使用下个节点作为最高峰；
   2. 当前节点小于等于上一节点，则当前节点的高度和一定小于等于上一节点，跳过当前节点。
3. 以当前节点为最高峰向左右边界遍历，返回最大的高度和。

代码展示

class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size();
        int[] a = maxHeights.stream().mapToInt(i -> i).toArray();
        long ans = 0L;
        for (int num = 0; num < n; num++) {
            if(num < n - 1 && a[num] < a[num + 1]){
                continue;
            }
            if(num > 0 && a[num] <= a[num - 1]) {
                continue;
            }
            int left = a[num];
            int right = left;
            long res = left;
            for (int i = num - 1; i >= 0; i--) {
                int temp = a[i];
                if (temp > left) {
                    res += left;
                } else {
                    left = temp;
                    res += temp;
                }
            }
            for (int i = num + 1; i < n; i++) {
                int temp = a[i];
                if (temp > right) {
                    res += right;
                } else {
                    res += temp;
                    right = temp;
                }
            }
            ans = Math.max(ans,res);
        }
        return ans;
    }
}