LeetCode 题解工作台
美丽塔 II
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。 如果以下条件满足，我们称这些塔是 美丽 的： 1 heights 是一个 山脉 数组。 如果存在下标 i 满足以下条件，那么我们称…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
我们定义 表示前 座塔中，以最后一座塔作为最高塔的美丽塔方案的高度和。我们可以得到如下的状态转移方程： $$
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个长度为 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 <= 1051 <= maxHeights[i] <= 109
解题思路
方法一：动态规划 + 单调栈
我们定义 表示前 座塔中，以最后一座塔作为最高塔的美丽塔方案的高度和。我们可以得到如下的状态转移方程：
其中 是最后一座塔左边第一个高度小于等于 的塔的下标。我们可以使用单调栈来维护这个下标。
我们可以使用类似的方法求出 ，表示从右往左，以第 座塔作为最高塔的美丽塔方案的高度和。最终答案即为 的最大值。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
n = len(maxHeights)
stk = []
left = [-1] * n
for i, x in enumerate(maxHeights):
while stk and maxHeights[stk[-1]] > x:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
right = [n] * n
for i in range(n - 1, -1, -1):
x = maxHeights[i]
while stk and maxHeights[stk[-1]] >= x:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
f = [0] * n
for i, x in enumerate(maxHeights):
if i and x >= maxHeights[i - 1]:
f[i] = f[i - 1] + x
else:
j = left[i]
f[i] = x * (i - j) + (f[j] if j != -1 else 0)
g = [0] * n
for i in range(n - 1, -1, -1):
if i < n - 1 and maxHeights[i] >= maxHeights[i + 1]:
g[i] = g[i + 1] + maxHeights[i]
else:
j = right[i]
g[i] = maxHeights[i] * (j - i) + (g[j] if j != n else 0)
return max(a + b - c for a, b, c in zip(f, g, maxHeights))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for understanding of stack-based state management.
- question_mark
Check if the candidate effectively handles peak identification and transitions.
- question_mark
Evaluate the candidate's ability to optimize the sum of tower heights within the constraints.
常见陷阱
外企场景- error
Failing to properly identify the peak of the mountain could lead to incorrect height configurations.
- error
Improper stack management can result in inefficient solutions or incorrect configurations.
- error
Overlooking edge cases where there are minimal towers or towers with extreme heights.
进阶变体
外企场景- arrow_right_alt
Allowing multiple peaks in the mountain configuration.
- arrow_right_alt
Handling constraints with a larger number of towers (n approaching 10^5).
- arrow_right_alt
Using alternative data structures for stack management like deque or priority queues.