#2865

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Beautiful Towers I

Solve Beautiful Towers I by testing each peak and enforcing mountain limits with monotonic stack style height propagation.

array stack monotonic stack

Problem Statement

In Beautiful Towers I, you start with maximum allowed heights for consecutive towers and may only remove bricks. You need to end with a skyline that first stays non-decreasing up to a peak region and then stays non-increasing after it. The peak can be one tower or several adjacent towers with the same final height, as long as no tower exceeds its original limit.

The goal is to maximize the total sum of final heights. A correct solution must respect the original cap at every index while handling the exact mountain restriction, which is where many wrong attempts fail: they pick a tall peak but do not properly propagate the smaller height limit across both sides.

Examples

Example 1

Input: heights = [5,3,4,1,1]

Output: 13

We remove some bricks to make heights = [5,3,3,1,1] , the peak is at index 0.

Example 2

Input: heights = [6,5,3,9,2,7]

Output: 22

We remove some bricks to make heights = [3,3,3,9,2,2] , the peak is at index 3.

Example 3

Input: heights = [3,2,5,5,2,3]

Output: 18

We remove some bricks to make heights = [2,2,5,5,2,2] , the peak is at index 2 or 3.

Constraints

1 <= n == heights.length <= 103
1 <= heights[i] <= 109

Solution Approach

Try every index as the peak

Because Beautiful Towers I has at most 1000 towers, a practical interview solution is to try each index i as the peak. Assume the final height at i stays at heights[i], then walk left and right while shrinking each next tower to the minimum of its own cap and the previous chosen height. That greedy propagation is forced once the peak is fixed, because any larger value would break the mountain shape, and any smaller value would only reduce the sum.

Build the best mountain for one fixed peak

For a chosen peak i, scan left from i-1 down to 0 with cur = min(cur, heights[j]) and add cur into the total. Then reset cur to heights[i], scan right from i+1 up to n-1 with the same min rule, and add those values. This exactly constructs the best valid mountain centered at i because each side should stay as tall as possible without increasing in the wrong direction.

See the monotonic stack pattern behind the brute force

Even though Beautiful Towers I can be solved by O(n^2) peak simulation, its core pattern is still stack-based state management. The repeated min propagation on each side is the same constraint a monotonic stack compresses in the harder optimization: when a new smaller height appears, earlier taller segments must collapse to that boundary. Recognizing that trade-off helps explain why Beautiful Towers II upgrades this idea to linear time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

If you test every index as the peak and scan both directions each time, the time complexity is O(n^2) and the extra space is O(1) beyond the running total. That is fast enough for Beautiful Towers I because n <= 1000. A stack-based precomputation can reduce repeated side work, but the direct peak simulation is the simplest correct match for this version.

What Interviewers Usually Probe

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.
Mentioning Array, Stack, and Monotonic Stack usually means they want more than brute force intuition: explain why decreasing boundaries collapse previous heights.
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.

Common Pitfalls or Variants

Common pitfalls

Using the original heights on one side without clamping by the previous chosen tower breaks the mountain rule and overcounts the answer.
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].
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.

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Enumeration

We can enumerate each tower as the tallest tower, each time expanding to the left and right, calculating the height of each other position, and then accumulating to get the height sum $t$. The maximum of all height sums is the answer.

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

Solution 2: Dynamic Programming + Monotonic Stack

Solution 1 is sufficient to pass this problem, but the time complexity is relatively high. We can use "Dynamic Programming + Monotonic Stack" to optimize the enumeration process.

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

Continue Practicing

#2866 beautiful towers ii #2818 apply operations to maximize score #2940 find building where alice and bob can meet