2866. 美丽塔 II (opens new window)

1.单调栈+前缀和

遍历列表，以每个坐标作为顶点，求出满足山脉数组定义的左右两侧的高度和，时间O(n*n)超时。

优化方法：预先求出以每个i为顶点的左右两侧前缀和。山脉数组的前缀和满足单调性质，可以采用单调栈来计算，找到前一个波峰。

class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        long res = Integer.MIN_VALUE;
        long[] prefix = new long[maxHeights.size()];
        long[] suffix = new long[maxHeights.size()];
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        for (int i = 0; i < maxHeights.size(); i++) {
            //前缀和
            while (!stack1.isEmpty()) {
                if(maxHeights.get(stack1.peek())>=maxHeights.get(i)) stack1.pop();
                else break;
            }
            prefix[i] = stack1.isEmpty() ? 1l*(i + 1) * maxHeights.get(i) : prefix[stack1.peek()] + 1l * (i - stack1.peek()) * maxHeights.get(i);
            stack1.push(i);
            //后缀和
            int k=maxHeights.size()-i-1;
            while (!stack2.isEmpty()) {
                if(maxHeights.get(stack2.peek())>=maxHeights.get(k)) stack2.pop();
                else break;
            }
            suffix[k] = stack2.isEmpty() ? 1l * (maxHeights.size() - k) * maxHeights.get(k) : suffix[stack2.peek()] + 1l * (stack2.peek() - k) * maxHeights.get(k);
            stack2.push(k);
        }

        for (int i = 0; i < maxHeights.size(); i++) {
            int pre=maxHeights.get(i);
            long sum=prefix[i]+suffix[i]-maxHeights.get(i);
            res = Math.max(res, sum);
        }
        return res;
    }
}