Practice/Bloomberg/Leetcode 2866. Beautiful Towers II

Leetcode 2866. Beautiful Towers II

CodingOptional

Problem

You are building a row of towers where each tower has a height constraint. Given an array maxHeights where maxHeights[i] represents the maximum possible height for tower i, you need to assign an actual height to each tower such that:

1. Each tower's height is in the range [1, maxHeights[i]]
2. The heights form a mountain pattern: they must be non-decreasing up to some peak index, then non-increasing after the peak
3. The sum of all tower heights is maximized

A mountain pattern means there exists some index peak where:

• Heights are non-decreasing from index 0 to peak: heights[0] <= heights[1] <= ... <= heights[peak]
• Heights are non-increasing from index peak to n-1: heights[peak] >= heights[peak+1] >= ... >= heights[n-1]

Return the maximum possible sum of heights that satisfies these constraints.

Requirements

1. Assign a height between 1 and maxHeights[i] to each tower i
2. Heights must form a valid mountain pattern (non-decreasing then non-increasing)
3. Maximize the total sum of all assigned heights
4. Handle the case where the peak can be at any position including the endpoints

Constraints

• 1 <= maxHeights.length <= 10^5
• 1 <= maxHeights[i] <= 10^9
• Time complexity should be O(n) or O(n log n)
• Space complexity should be O(n)

Examples

Example 1:

Input: maxHeights = [5, 3, 4, 1, 1] Output: 13 Explanation: Choose heights [5, 3, 3, 1, 1] with peak at index 0. The pattern is non-increasing throughout: 5 >= 3 >= 3 >= 1 >= 1 Sum = 5 + 3 + 3 + 1 + 1 = 13

Example 2:

Input: maxHeights = [6, 5, 3, 9, 2, 7] Output: 22 Explanation: Choose heights [3, 3, 3, 9, 2, 2] with peak at index 3. Non-decreasing: 3 <= 3 <= 3 <= 9 Non-increasing: 9 >= 2 >= 2 Sum = 3 + 3 + 3 + 9 + 2 + 2 = 22

Example 3:

Input: maxHeights = [3, 2, 5, 5, 2, 3] Output: 18 Explanation: Choose heights [2, 2, 5, 5, 2, 2] with peak at index 2 or 3. Sum = 2 + 2 + 5 + 5 + 2 + 2 = 18