LC 2865. 美丽塔 I

发布时间:2024年01月24日

2865. 美丽塔 I

难度 : 中等

题目大意

给你一个长度为 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 <= n == maxHeights <= 10^3
  • 1 <= maxHeights[i] <= 10^9

示例 1:

输入:maxHeights = [5,3,4,1,1]
输出:13
解释:和最大的美丽塔方案为 heights = [5,3,3,1,1] ,这是一个美丽塔方案,因为:
- 1 <= heights[i] <= maxHeights[i]  
- heights 是个山脉数组,峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。

分析

根据数据范围可以知道时间复杂度要控制在 O ( n 2 l o g n ) O(n^2logn) O(n2logn),首先我们要确定这个山脉的中心,也就是说我们可以枚举这个中心,然后去构造这个山脉数组,至于怎么构造,因为确定了中心,所以我们可以枚举左右两边,以左边为例,我们要所得的山脉的高度之和最大,所以我们要尽可能取到最大的山脉高度,也就是说,如果当前山脉的最大高度小于等于右边山脉的高度,我们就可以直接取最大的高度,如果比右边的高度高,那么就只能取和右边的山脉相同的高度,右边是同理的,注意数据范围可能爆int,所以注意开long long

暴力枚举

class Solution {
public:
    using LL = long long;
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int n = maxHeights.size();
        LL res = 0;
        for (int i = 0; i < n; i ++)
        {
            LL sum = maxHeights[i];
            LL t = maxHeights[i];// 用t表示当前山脉的限制高度
            for (int j = i - 1; j >= 0; j --)
                if (maxHeights[j] <= t) sum += maxHeights[j], t = maxHeights[j];
                else sum += t;
            t = maxHeights[i];
            for (int j = i + 1; j < n; j ++)
                if (maxHeights[j] <= t) sum += maxHeights[j], t = maxHeights[j];
                else sum += t;
            res = max(res, sum);
        }
        return res;
    }
};

时间复杂度 O ( n 2 ) O(n^2) O(n2)

分析

我们确定山峰之后,分析左边,从山峰往左看,根据上面的暴力做法的提示,我们发现,假设当前的山峰maxHeightx,那么如果左边的山脉是高于x的,左边的山脉就会受到限制,那么这个限制什么时候解除呢,碰到一个比x还要小的山脉,而且是第一个,那么我们就可以联想到单调栈的思想,我们可以存下标,我们首先找到受x限制的那一段,终点下标就是栈顶假设是t,那么这一段全部都是x高度,我们定义l[i]表示当前位置为山峰,从i往左看非递增的山脉的高度值和,假设l[i] = l[t] + (i - t) * x(下标从1开始),考虑边界情况,如果左边没有比x小的,那么左边都要受到限制,所以我们可以将栈底始终放一个下标0,这样就方便处理,至于右边的情况,是一样的,我们可以将数组反转一下,然后就是相同的处理

单调栈

class Solution {
public:
    using LL = long long;
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int n = maxHeights.size();
        vector<LL> l(n + 1), r(n + 1); // 下标从1开始方便处理边界
        auto f = [&](vector<LL>& g) {
            stack<LL> stk;
            stk.push(0); // 方便处理边界
            for (int i = 1; i <= n; i ++ ) {
                while (stk.size() > 1 && maxHeights[stk.top() - 1] >= maxHeights[i - 1]) stk.pop();
                g[i] = g[stk.top()] + (LL)(i - stk.top()) * maxHeights[i - 1];
                stk.push(i);
            }
        };
        f(l), reverse(maxHeights.begin(), maxHeights.end()), f(r);
        LL res = 0;
        for (int i = 1; i <= n; i ++) {
            res = max(res, l[i] + r[n - i + 1] - maxHeights[n - i]); // 注意此时数组已经反转了,所以下标要注意
        }
        return res;
    }
};

时间复杂度: O ( n ) O(n) O(n)

结束了

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