1. Beautiful Towers II (LeetCode)
Model answer
The task
Choose a height for each tower that does not exceed its individual maximum, so the heights rise to a peak and then fall. Return the largest possible sum of the chosen heights.
Key idea
For each possible peak, compute the best sum extending left and right while respecting the mountain shape. A monotonic stack finds where each side’s height is limited by a previous or next tower, allowing all peak totals to be computed in linear time.
Approach
- Scan left to right, maintaining a stack of indices with nondecreasing maximum heights.
- For each index, use the nearest earlier height no greater than its own to calculate the best left-side sum.
- Scan right to left in the same way to calculate the best right-side sum.
- Treat each tower as the peak; add its left and right sums, subtracting its height once because it appears in both.
- Return the largest resulting total.
from typing import List
class Solution:
def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
n = len(maxHeights)
left = [0] * n
right = [0] * n
# Best sum from the start through each index,
# with heights nondecreasing toward that index.
stack = []
for i, height in enumerate(maxHeights):
while stack and maxHeights[stack[-1]] > height:
stack.pop()
if stack:
prev = stack[-1]
left[i] = left[prev] + height * (i - prev)
else:
left[i] = height * (i + 1)
stack.append(i)
# Best sum from each index through the end,
# with heights nonincreasing away from that index.
stack = []
for i in range(n - 1, -1, -1):
height = maxHeights[i]
while stack and maxHeights[stack[-1]] > height:
stack.pop()
if stack:
nxt = stack[-1]
right[i] = right[nxt] + height * (nxt - i)
else:
right[i] = height * (n - i)
stack.append(i)
return max(left[i] + right[i] - maxHeights[i] for i in range(n))
Complexity:
- Time: O(n), since each index is pushed and popped at most once in each scan.
- Space: O(n), for the two sum arrays and the stacks.
Common follow-ups
- Can the auxiliary arrays be reduced? Yes; process candidate peaks while keeping only the needed stack sums.
- What if multiple peaks give the same maximum? Any of them is valid; the algorithm returns their shared maximum sum.
- Why subtract the peak height? It is included in both the left-side and right-side sums.