Beautiful Towers II
Problem
Given maxHeights, build towers with heights 1 ≤ heights[i] ≤ maxHeights[i] so that the heights form a mountain: they never decrease up to some peak index, then never increase after it. Return the maximum possible total height of such a beautiful configuration.
For a fixed peak i, the prefix 0..i must be non-decreasing and the suffix i..n−1 non-increasing. To maximize the sum, each side greedily takes the largest height allowed by every cap seen so far — a classic monotonic-stack computation.
maxHeights = [5,3,4,1,1]13def maximumSumOfHeights(maxHeights):
n = len(maxHeights)
# prefix[i]: best sum of 0..i, non-decreasing, ending at maxHeights[i]
prefix = [0] * n
stack = [] # indices, increasing height
for i in range(n):
while stack and maxHeights[stack[-1]] > maxHeights[i]:
stack.pop() # these caps are dragged down to h[i]
j = stack[-1] if stack else -1
prefix[i] = prefix[j] + (i - j) * maxHeights[i] if j >= 0 \
else (i + 1) * maxHeights[i]
stack.append(i)
# suffix[i]: best sum of i..n-1, non-increasing, starting at maxHeights[i]
suffix = [0] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and maxHeights[stack[-1]] > maxHeights[i]:
stack.pop()
j = stack[-1] if stack else n
suffix[i] = suffix[j] + (j - i) * maxHeights[i] if j < n \
else (n - i) * maxHeights[i]
stack.append(i)
best = 0
for i in range(n): # peak at i: add both sides, drop double count
best = max(best, prefix[i] + suffix[i] - maxHeights[i])
return bestfunction maximumSumOfHeights(maxHeights) {
const n = maxHeights.length;
const prefix = new Array(n).fill(0); // best sum of 0..i, non-decreasing
let stack = []; // indices, increasing height
for (let i = 0; i < n; i++) {
while (stack.length && maxHeights[stack[stack.length - 1]] > maxHeights[i])
stack.pop(); // drag taller caps down to h[i]
const j = stack.length ? stack[stack.length - 1] : -1;
prefix[i] = j >= 0 ? prefix[j] + (i - j) * maxHeights[i]
: (i + 1) * maxHeights[i];
stack.push(i);
}
const suffix = new Array(n).fill(0); // best sum of i..n-1, non-increasing
stack = [];
for (let i = n - 1; i >= 0; i--) {
while (stack.length && maxHeights[stack[stack.length - 1]] > maxHeights[i])
stack.pop();
const j = stack.length ? stack[stack.length - 1] : n;
suffix[i] = j < n ? suffix[j] + (j - i) * maxHeights[i]
: (n - i) * maxHeights[i];
stack.push(i);
}
let best = 0;
for (let i = 0; i < n; i++) // peak at i, drop the double count
best = Math.max(best, prefix[i] + suffix[i] - maxHeights[i]);
return best;
}long maximumSumOfHeights(List<Integer> maxHeights) {
int n = maxHeights.size();
long[] prefix = new long[n]; // best sum of 0..i, non-decreasing
Deque<Integer> stack = new ArrayDeque<>(); // indices, increasing height
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && maxHeights.get(stack.peek()) > maxHeights.get(i))
stack.pop(); // drag taller caps down to h[i]
int j = stack.isEmpty() ? -1 : stack.peek();
prefix[i] = j >= 0 ? prefix[j] + (long)(i - j) * maxHeights.get(i)
: (long)(i + 1) * maxHeights.get(i);
stack.push(i);
}
long[] suffix = new long[n]; // best sum of i..n-1, non-increasing
stack = new ArrayDeque<>();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && maxHeights.get(stack.peek()) > maxHeights.get(i))
stack.pop();
int j = stack.isEmpty() ? n : stack.peek();
suffix[i] = j < n ? suffix[j] + (long)(j - i) * maxHeights.get(i)
: (long)(n - i) * maxHeights.get(i);
stack.push(i);
}
long best = 0;
for (int i = 0; i < n; i++) // peak at i, drop the double count
best = Math.max(best, prefix[i] + suffix[i] - maxHeights.get(i));
return best;
}long long maximumSumOfHeights(vector<int>& maxHeights) {
int n = maxHeights.size();
vector<long long> prefix(n, 0); // best sum of 0..i, non-decreasing
vector<int> stack; // indices, increasing height
for (int i = 0; i < n; i++) {
while (!stack.empty() && maxHeights[stack.back()] > maxHeights[i])
stack.pop_back(); // drag taller caps down to h[i]
int j = stack.empty() ? -1 : stack.back();
prefix[i] = j >= 0 ? prefix[j] + (long long)(i - j) * maxHeights[i]
: (long long)(i + 1) * maxHeights[i];
stack.push_back(i);
}
vector<long long> suffix(n, 0); // best sum of i..n-1, non-increasing
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.empty() && maxHeights[stack.back()] > maxHeights[i])
stack.pop_back();
int j = stack.empty() ? n : stack.back();
suffix[i] = j < n ? suffix[j] + (long long)(j - i) * maxHeights[i]
: (long long)(n - i) * maxHeights[i];
stack.push_back(i);
}
long long best = 0;
for (int i = 0; i < n; i++) // peak at i, drop the double count
best = max(best, prefix[i] + suffix[i] - maxHeights[i]);
return best;
}Explanation
Every beautiful configuration has exactly one peak. If we fix the peak index i, the heights to its left must be non-decreasing and the heights to its right non-increasing, with everything capped by maxHeights. So the answer is the best over all choices of peak.
The trick is computing each peak's value fast. prefix[i] is the maximum sum of heights for positions 0..i when the heights are non-decreasing and heights[i] = maxHeights[i]. Greedily, every position to the left should be as tall as possible while not exceeding any cap between it and i. The value just to the left where the cap drops below maxHeights[i] is the natural break point.
A monotonic stack of indices with increasing heights finds that break point. When we reach i, we pop every index whose cap is taller than maxHeights[i] — those positions get pulled down to maxHeights[i]. The remaining top j is the previous-smaller index, so prefix[i] = prefix[j] + (i − j) * maxHeights[i]. If the stack empties, the whole prefix is flattened to maxHeights[i], giving (i + 1) * maxHeights[i].
suffix[i] is the mirror image, computed by scanning right to left with the same stack idea. Finally, for each peak we combine the two sides: prefix[i] + suffix[i] − maxHeights[i], subtracting once because the peak is counted in both halves.
Example: [5,3,4,1,1]. Peak at index 0 forces a fully non-increasing array [5,3,3,1,1] summing to 13, which beats every other peak choice.