【每日一题】美丽塔 II

2023-12-21 14:20:09

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 ) O(n^2) O(n2) n n n 为数组 maxHeight 的长度,对于规模为 1 0 3 10^3 103 甚至 1 0 4 10^4 104 的数据量,该方法可以顺利通过,对于更大规模的数据比如 1 0 5 10^5 105,暴力枚举的方法一定超时,时间复杂度 O ( n ) O(n) O(n) 的解法请看 方法二

空间复杂度: O ( 1 ) O(1) O(1)

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

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

maxHeight 简化为 nums

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

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

接下来看一下如何计算数组 presuf

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

我们先计算 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 中的 5sum = 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 中的 4sum = 10 - 4 = 6,接着弹出 1 并撤销 sum 中的 23sum = 6 - 2 * 3 = 0;当前和 sum = 0 + 1 * (3 - (-1)) = 4;更新 pre[3] = 4,将 3 加入单调栈 st 中。

(6)i = 4:执行 while 循环,st 弹出 3,撤销 sum 中的 41sum = 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 ) O(n) O(n) n n n 为数组 nums 的长度。

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

文章来源:https://blog.csdn.net/weixin_54383080/article/details/135128015
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。