网站公司成本,免费网站注册com,小清新 轻音乐网站 wordpress,今天进京最新通知2865. 美丽塔 I
难度 : 中等
题目大意 给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i #xff0c;高度为 heights[i] 。 如果以下条件满足#xff0c;我们称这些塔是 美丽 的#xff1a; 1 heights…2865. 美丽塔 I
难度 : 中等
题目大意 给你一个长度为 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] 请你返回满足 美丽塔 要求的方案中高度和的最大值 。 提示 1 n maxHeights 10^31 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(vectorint 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)
分析
我们确定山峰之后分析左边从山峰往左看根据上面的暴力做法的提示我们发现假设当前的山峰maxHeight是x那么如果左边的山脉是高于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(vectorint maxHeights) {int n maxHeights.size();vectorLL l(n 1), r(n 1); // 下标从1开始方便处理边界auto f [](vectorLL g) {stackLL 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)
结束了
