# 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:

```python
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。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/2866.beautiful-towers-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.