400. Tallest Mountain Towers
A developer is building a row of towers in a game. Tower i may be given any whole height from 1 up to maxHeights[i]. The finished skyline must look like a mountain: there is a peak position p such that heights never decrease when walking from the left end to p, and never increase when walking from p to the right end.
Choose the heights so that the total height of all towers is as large as possible, and return that total. The total can exceed the range of a 32-bit integer. Trying every peak and extending in both directions costs O(n^2); a monotonic stack lets you obtain the best left part and right part for every peak in linear time.
Example 1
- Input:
- maxHeights = [4,9,5,8,3]
- Output:
- 26
- Explanation:
With the peak at index 1 the heights 4, 9, 5, 5, 3 are allowed and sum to 26, which beats every other peak.
Example 2
- Input:
- maxHeights = [6,2,7]
- Output:
- 11
- Explanation:
Peak at index 2: the earlier towers are limited by the 2, giving 2, 2, 7 = 11. A peak at index 0 gives only 6 + 2 + 2 = 10.
Constraints
1 ≤ maxHeights.length ≤ 105
1 ≤ maxHeights[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)