2866.beautiful-towers-ii.md

题目地址(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。