【每日一题】美丽塔 II

Tag

【单调栈】【数组】【2023-12-21】

---

题目来源

2866. 美丽塔 II

---

题目解读

题目意思相对明确，所谓的美丽塔数组就是山状数组，即有一个高度为 maxHeight[i] 的山峰，山峰两侧的高度要小于 maxHeight[i] 并且小于各自的允许高度。需要找出满足以上条件的美丽塔数组，返回数组和。

---

方法一：暴力枚举

暴力枚举即以每一个整数元素作为山峰，对左右两侧的山峰高度依次处理，取出所有山峰中美丽塔数组的最大值。处理规则如下：

• 当前的最高山峰下标为 i，此处山峰高度为 maxHeight[i]；当前山峰美丽塔的最大值为 res = maxHeight[i]；
• 从下标 i-1 处开始枚举山峰左侧的高度 maxHeight[i-1]，如果 maxHeight[i-1] <= maxHeight[i]，则下标 i-1 处的山峰高度最大为 maxHeight[i-1]，否则下标 i-1 处的山峰高度最大为 maxHeight[i]，其实 i-1 处的山峰高度最大为 min(maxHeight[i-1], maxHeight[i])。加到 res 中，枚举完山峰 i 左侧的山，即可得到以下标 i 为山峰的左侧山的高度最大值。
• 同理，可以得到以下标 i 为山峰的右侧山的高度最大值。
• 最后，选出枚举所有山峰得到的最大值作为最后的答案。

复杂度分析

时间复杂度：$O(n^2)$，$n$ 为数组 maxHeight 的长度，对于规模为 $10^3$ 甚至 $10^4$ 的数据量，该方法可以顺利通过，对于更大规模的数据比如 $10^5$，暴力枚举的方法一定超时，时间复杂度 $O(n)$ 的解法请看 方法二。

空间复杂度：$O(1)$。

方法二：前后缀分解+单调栈

前、后缀的方法在做题时候想到了，但是一直没想通如何计算前、后缀，经过 前后缀分解+单调栈（Python/Java/C++/Go） 思路点拨之后，豁然开朗。

把 maxHeight 简化为 nums。

我们可以借助前后缀的思想，提前计算山峰左侧的递增段的最大和以及山峰右侧递减段最大和。

我们使用数组 pre[i] 表示山峰 nums[i] 左侧的递增段的最大和，使用数组 suf[i] 表示山峰右侧递减段最大和。那么最终的答案为 pre[i] + suf[i+1] 的最大值。

接下来看一下如何计算数组 pre 和 suf。

使用单调栈，元素值从栈底到栈顶严格递增。

我们先计算 pre，从左到右遍历数组 nums，设当前的元素和为 sum。

• 如果 nums[i] 大于栈顶元素，直接将 nums[i] 加到 sum 中，同时把 i 入栈（栈中只需要保存下标）；
• 否则，只要 nums[i] 小于等于栈顶的元素值，就不断循环，撤销掉原先加入到 sum 中的值。循环结束后，从 nums[i] 到 nums[j-1]（假设现在的栈顶下标是 j） 的值都必须是 nums[i]，把 nums[i] * (j - i) 加到 sum 中。

现在以数组 nums = [5, 3, 4, 1, 1] 为例，用图示来模拟上述计算 pre[i] 的过程。

（1）初始化单调栈 st，并放入哨兵 -1；

（2）遍历数组 nums 开始计算，当前 i = 0：栈 s 的长度为 1 不满足大于 1 的要求，跳过 while 循环；计算当前和 sum = 0 + nums[i] * (i - st.top()) = 5 * (0 - (-1)) = 5；更新 pre[0] = 5，将 0 加入单调栈 st 中。

（3）i = 1：执行 while 循环，st 弹出 0，撤销 sum 中的 5 即 sum = 5 - 5 = 0；当前和 sum = 0 + 3 * (1 - (-1)) = 6；更新 pre[1] = 6，将 1 加入单调栈 st 中。

（4）i = 2：不需要执行 while 循环；当前和 sum = 4 + 3 * (2 - 1) = 10；更新 pre[2] = 10，将 2 加入单调栈 st 中。

（5）i = 3：执行 while 循环，st 弹出 2，先撤销 sum 中的 4 即 sum = 10 - 4 = 6，接着弹出 1 并撤销 sum 中的 2 个 3 即 sum = 6 - 2 * 3 = 0；当前和 sum = 0 + 1 * (3 - (-1)) = 4；更新 pre[3] = 4，将 3 加入单调栈 st 中。

（6）i = 4：执行 while 循环，st 弹出 3，撤销 sum 中的 4 个 1 即 sum = 4 - 1 * (3 - (-1)) = 0；当前和 sum = 0 + 1 * (4 - (-1)) = 5；更新 pre[4] = 5，将 1 加入单调栈 st 中。

（7）数组 pre 计算完成，pre[i] = [5, 6, 10, 4, 5]。

数组 suf 的计算同理，这时候需要从右往左遍历。

实现代码

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& nums) {
        int n = nums.size();
        vector<long long> pre(n), suf(n+1);

        stack<int> st;
        st.push(-1);    // 哨兵
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            while (st.size() > 1 && x <= nums[st.top()]) {
                int j = st.top();
                st.pop();
                sum -= (long long) nums[j] * (j - st.top());
            }
            sum += (long long) x * (i - st.top());
            pre[i] = sum;
            st.push(i);
        }

        st = stack<int>(); sum = 0;
        st.push(n); // 哨兵
        for (int i = n-1; i >= 0; --i) {
            int x = nums[i];
            while (st.size() > 1 && x <= nums[st.top()]) {
                int j = st.top();
                st.pop();
                sum -= (long long) nums[j] * (st.top() - j);
            }
            sum += (long long) x * (st.top() - i);
            suf[i] = sum;
            st.push(i);
        }

        long long res = 0;
        for (int i = 0; i < n; ++i) {
            res = max(res, pre[i] + suf[i+1]);
        }
        return res;
    }
};

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 nums 的长度。

空间复杂度：$O(n)$，使用的额外空间为记录山峰左侧的最大和。