What is the main idea for Beautiful Towers I?

Try every index as the peak, then greedily propagate outward with running minimums on both sides. Once the peak is fixed, that gives the tallest valid mountain and therefore the best sum for that peak.

Why does greedy min propagation work for a fixed peak?

Each side must stay monotone relative to the peak and cannot exceed the original height cap. So at every step, the tallest legal choice is exactly the minimum of the current cap and the previous chosen tower height.

Is Beautiful Towers I a monotonic stack problem or just brute force?

The simplest accepted solution is brute force over all peaks with O(n^2) time. But the underlying pattern is monotonic stack style state management because smaller heights force earlier taller segments to collapse, which is the same idea used in faster versions.

Why is the answer 13 for heights = [5,3,4,1,1]?

Using index 0 as the peak gives the best mountain. Propagating right with running minimums turns the array into [5,3,3,1,1], whose sum is 13, and no other peak produces a larger valid total.

What mistake most often causes wrong answers in this pattern?

A common bug is treating the left and right scans independently without carrying the previous chosen height. That allows illegal increases away from the peak or toward it, which makes the computed mountain sum too large.

#2865

Medium

auto_awesome栈·状态

LeetCode 题解工作台

美丽塔 I

给定一个包含 n 个整数的数组 heights 表示 n 座连续的塔中砖块的数量。你的任务是移除一些砖块来形成一个山脉状的塔排列。在这种布置中，塔高度先是非递减，有一个或多个连续塔达到最大峰值，然后非递增排列。返回满足山脉状塔排列的方案中，高度和的最大值。示例 1：输入： maxHei…

数组栈单调栈

题目描述

给定一个包含 n 个整数的数组 heights 表示 n 座连续的塔中砖块的数量。你的任务是移除一些砖块来形成一个 山脉状 的塔排列。在这种布置中，塔高度先是非递减，有一个或多个连续塔达到最大峰值，然后非递增排列。

返回满足山脉状塔排列的方案中，高度和的最大值 。

示例 1：

输入：maxHeights = [5,3,4,1,1]
输出：13
解释：我们移除一些砖块来形成 heights = [5,3,3,1,1]，峰值位于下标 0。

示例 2：

输入：maxHeights = [6,5,3,9,2,7]
输出：22
解释：我们移除一些砖块来形成 heights = [3,3,3,9,2,2]，峰值位于下标 3。

示例 3：

输入：maxHeights = [3,2,5,5,2,3]
输出：18
解释：我们移除一些砖块来形成 heights = [2,2,5,5,2,2]，峰值位于下标 2 或 3。

提示：

1 <= n == heights.length <= 10³
1 <= heights[i] <= 10⁹

lightbulb

解题思路

方法一：枚举

我们可以枚举每一座塔作为最高塔，每一次向左右两边扩展，算出其他每个位置的高度，然后累加得到高度和 $t$ 。求出所有高度和的最大值即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 $maxHeights$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        ans, n = 0, len(maxHeights)
        for i, x in enumerate(maxHeights):
            y = t = x
            for j in range(i - 1, -1, -1):
                y = min(y, maxHeights[j])
                t += y
            y = x
            for j in range(i + 1, n):
                y = min(y, maxHeights[j])
                t += y
            ans = max(ans, t)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The hint to try every possible peak means the interviewer expects you to notice that one fixed peak forces greedy min propagation on both sides.
question_mark
Mentioning Array, Stack, and Monotonic Stack usually means they want more than brute force intuition: explain why decreasing boundaries collapse previous heights.
question_mark
If they ask how this scales beyond n = 1000, they are probing whether you can connect Beautiful Towers I to the monotonic stack optimization pattern.

warning

常见陷阱

外企场景

error
Using the original heights on one side without clamping by the previous chosen tower breaks the mountain rule and overcounts the answer.
error
Forgetting that equal heights are allowed causes wrong rejection of flat peak regions such as the best arrangement in [3,2,5,5,2,3].
error
Trying to greedily choose the globally tallest tower as the peak can miss the best total because a slightly lower peak may preserve much larger sides.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual final mountain array instead of only the maximum sum after choosing the best peak.
arrow_right_alt
Allow increasing some towers as well as removing bricks, which changes the fixed-cap logic and breaks the same greedy side propagation.
arrow_right_alt
Scale the same mountain-sum objective to large n, where monotonic stack precomputation becomes the intended optimization.

help

常见问题

外企场景

继续练习

#2866 美丽塔 II #2818 操作使得分最大 #2940 找到 Alice 和 Bob 可以相遇的建筑