Links

2866. 美丽塔 II

题目地址(2866. 美丽塔 II)

https://leetcode.cn/problems/beautiful-towers-ii/description/

题目描述

给你一个长度为 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:
输入:maxHeights = [5,3,4,1,1]
输出:13
解释:和最大的美丽塔方案为 heights = [5,3,3,1,1] ,这是一个美丽塔方案,因为:
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山状数组,峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。
示例 2:
输入:maxHeights = [6,5,3,9,2,7]
输出:22
解释: 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ,这是一个美丽塔方案,因为:
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山状数组,峰值在 i = 3 处。
22 是所有美丽塔方案中的最大高度和。
示例 3:
输入:maxHeights = [3,2,5,5,2,3]
输出:18
解释:和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ,这是一个美丽塔方案,因为:
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山状数组,最大值在 i = 2 处。
注意,在这个方案中,i = 3 也是一个峰值。
18 是所有美丽塔方案中的最大高度和。
提示:
1 <= n == maxHeights <= 105
1 <= maxHeights[i] <= 109

前置知识

  • 动态规划
  • 单调栈

思路

这是一个为数不多的 2000 多分的中等题,难度在中等中偏大。
枚举 i 作为顶峰,其取值贪心的取 maxHeight[i]。关键是左右两侧如何取。由于左右两侧逻辑没有本质区别, 不妨仅考虑左边,然后套用同样的方法处理右边。
定义 f[i] 表示 i 为峰顶,左侧高度和最大值。我们可以递推地计算出所有 f[i] 的值。同理 g[i] 表示 i 为峰顶,右侧高度和最大值。
当 f 和 g 都已经处理好了,那么枚举 f[i] + g[i] - maxHeight[i] 的最大值即可。之所以减去 maxHeight[i] 是因为 f[i] 和 g[i] 都加上了当前位置的高度 maxHeight[i],重复了。
那么现在剩下如何计算 f 数组,也就是递推公式是什么。
我们用一个单调栈维护处理过的位置,对于当前位置 i,假设其左侧第一个小于它的位置是 l,那么 [l + 1, i] 都是大于等于 maxHeight[i] 的, 都可以且最多取到 maxHeight[i]。可以得到递推公式 f[i] = f[l] + (i - l) * maxHeight[i]

代码

  • 语言支持:Python3
Python3 Code:
class Solution:
def maximumSumOfHeights(self, maxHeight: List[int]) -> int:
# 枚举 i 作为顶峰,其取值贪心的取 maxHeight[i]
# 其左侧第一个小于它的位置 l,[l + 1, i] 都可以且最多取到 maxHeight[i]
n = len(maxHeight)
f = [-1] * n # f[i] 表示 i 为峰顶,左侧高度和最大值
g = [-1] * n # g[i] 表示 i 为峰顶,右侧高度和最大值
def cal(f):
st = []
for i in range(len(maxHeight)):
while st and maxHeight[i] < maxHeight[st[-1]]:
st.pop()
# 其左侧第一个小于它的位置 l,[l + 1, i] 都可以且最多取到 maxHeight[i]
if st:
f[i] = (i - st[-1]) * maxHeight[i] + f[st[-1]]
else:
f[i] = maxHeight[i] * (i + 1)
st.append(i)
cal(f)
maxHeight = maxHeight[::-1]
cal(g)
maxHeight = maxHeight[::-1]
ans = 0
for i in range(len(maxHeight)):
ans = max(ans, f[i] + g[n - 1 - i] - maxHeight[i])
return ans
复杂度分析
令 n 为数组长度
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$
f 和 g 以及 st 都使用 n 的空间。并且我们仅遍历了 maxHeights 数组三次,因此时间和空间复杂度都是 n。