【Leetcode 2866】美丽塔II —— 单调栈

2866. 美丽塔 II

给你一个长度为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]
请你返回满足 美丽塔 要求的方案中，高度和的最大值

题目分析

由题目可知，对于每个索引i，可以将数组分为两部分处理，即保证数组的左侧构成非递减，右侧构成非递增。最常使用的就是单调栈，意为在栈的「先进后出」规则基础上，要求「从 栈顶 到 栈底 的元素是单调递增（或者单调递减）」。

单调栈详解及相关 Leetcode 题解见 Leetcode 单调栈详解

为了使得数组元素尽可能大，此时heights[i]应取值为maxHeights[i]，设区间[0,i]构成的非递减数组元素和最大值为prefix[i]，区间 [i,n?1]构成的非递增数组元素和最大值为suffix[i]，此时构成的山状数组的元素之和即为prefix[i] + suffix[i] ? maxHeights[i]

/**
* 前缀和后缀分别构造两个单调递减栈，将 maxHeights 依次入栈，对于第 i 个元素来说，不断从栈顶弹出元素，直到栈顶元素小于等于 maxHeights[i]
 */
public long maximumSumOfHeights(List<Integer> maxHeights) {
    int n = maxHeights.size();
    long res = 0;
    long[] prefix = new long[n];
    long[] suffix = new long[n];
    Deque<Integer> stack1 = new ArrayDeque<Integer>();
    Deque<Integer> stack2 = new ArrayDeque<Integer>();

    for(int i = 0; i < n; i++){
        while(!stack1.isEmpty() && maxHeights.get(i) < maxHeights.get(stack1.peek())){
            stack1.pop();
        }
        prefix[i] = stack1.isEmpty() ? (long) (i + 1) * maxHeights.get(i) :
            prefix[stack1.peek()] + (long) (i - stack1.peek()) * maxHeights.get(i);
        stack1.push(i);
    }

    for(int i = n - 1; i >= 0; i--){
        while(!stack2.isEmpty() && maxHeights.get(i) < maxHeights.get(stack2.peek())){
            stack2.pop();
        }
        suffix[i] = stack2.isEmpty() ? (long) (n - i) * maxHeights.get(i) :
            suffix[stack2.peek()] + (long) (stack2.peek() - i) * maxHeights.get(i);
        stack2.push(i);
        res = Math.max(res, prefix[i] + suffix[i] - maxHeights.get(i));
    }
    return res;
}