#2866

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Beautiful Towers II

Maximize tower configurations with the stack-based approach while ensuring mountain-like patterns in this medium difficulty problem.

array stack monotonic stack

Problem Statement

You are given a 0-indexed array maxHeights consisting of n integers. Each integer represents the maximum allowable height for a tower at that index on a coordinate line. You need to construct a sequence of tower heights such that the heights form a mountain-like pattern and the sum of heights is maximized.

A configuration is considered beautiful if the sequence of tower heights forms a mountain-like shape with the peak at some index, and each tower height must lie between 1 and its corresponding value in maxHeights. Your task is to find the maximum possible sum of the tower heights that forms a beautiful configuration.

Examples

Example 1

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

Output: 13

One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:

1 <= heights[i] <= maxHeights[i]
heights is a mountain of peak i = 0. It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.

Example 2

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

Output: 22

One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:

1 <= heights[i] <= maxHeights[i]
heights is a mountain of peak i = 3. It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.

Example 3

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

Output: 18

One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:

1 <= heights[i] <= maxHeights[i]
heights is a mountain of peak i = 2. Note that, for this configuration, i = 3 can also be considered a peak. It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.

Constraints

1 <= n == maxHeights.length <= 105
1 <= maxHeights[i] <= 109

Solution Approach

Peak Identification

Start by considering each index as a potential peak of the mountain. For each candidate peak, the height of towers on both sides must decrease as you move away from the peak. This allows you to maintain the mountain shape.

Stack-Based Management

Use a stack to manage the tower heights efficiently. The stack helps ensure that each tower height is constrained by its respective maximum height and the mountain-like pattern is maintained. As you process each tower, adjust its height based on the current state of the stack.

Maximizing Heights

For each peak, calculate the maximum possible sum of tower heights that respects the constraints. The process involves determining the largest valid height configuration that forms a beautiful sequence by traversing from the peak outward.

Complexity Analysis

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

The time and space complexity depend on the final approach chosen for peak identification and stack-based management. Typically, this problem can be solved in O(n) time using a monotonic stack for efficient height management.

What Interviewers Usually Probe

Look for understanding of stack-based state management.
Check if the candidate effectively handles peak identification and transitions.
Evaluate the candidate's ability to optimize the sum of tower heights within the constraints.

Common Pitfalls or Variants

Common pitfalls

Failing to properly identify the peak of the mountain could lead to incorrect height configurations.
Improper stack management can result in inefficient solutions or incorrect configurations.
Overlooking edge cases where there are minimal towers or towers with extreme heights.

Follow-up variants

Allowing multiple peaks in the mountain configuration.
Handling constraints with a larger number of towers (n approaching 10^5).
Using alternative data structures for stack management like deque or priority queues.

FAQ

How do I approach solving the Beautiful Towers II problem?

Start by identifying each potential peak and then use a stack to manage the heights, ensuring they form a mountain-like configuration.

What is the time complexity of the solution?

The time complexity typically depends on the stack management approach, which can be done in O(n) time for this problem.

What are common pitfalls when solving this problem?

Common pitfalls include failing to identify the peak correctly or mismanaging the stack, leading to incorrect results.

Can I use other data structures to solve this problem?

Yes, alternatives like deques or priority queues can also be used for efficient stack management in this problem.

How can GhostInterview help with Beautiful Towers II?

GhostInterview provides step-by-step explanations of the stack-based approach, guiding you to a correct and efficient solution.

terminal

Solution

Solution 1: Dynamic Programming + Monotonic Stack

We define $f[i]$ to represent the height sum of the beautiful tower scheme with the last tower as the tallest tower among the first $i+1$ towers. We can get the following state transition equation:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

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))

Continue Practicing

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