Welcome to Subscribe On Youtube
2866. Beautiful Towers II
Description
You are given a 0-indexed array maxHeights of n integers.
You are tasked with building n towers in the coordinate line. The ith tower is built at coordinate i and has a height of heights[i].
A configuration of towers is beautiful if the following conditions hold:
1 <= heights[i] <= maxHeights[i]heightsis a mountain array.
Array heights is a mountain if there exists an index i such that:
- For all
0 < j <= i,heights[j - 1] <= heights[j] - For all
i <= k < n - 1,heights[k + 1] <= heights[k]
Return the maximum possible sum of heights of a beautiful configuration of towers.
Example 1:
Input: maxHeights = [5,3,4,1,1] Output: 13 Explanation: 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 Explanation: 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 Explanation: 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 <= 1051 <= maxHeights[i] <= 109
Solutions
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:
\[f[i]= \begin{cases} f[i-1]+heights[i],&\text{if } heights[i]\geq heights[i-1]\\ heights[i]\times(i-j)+f[j],&\text{if } heights[i]<heights[i-1] \end{cases}\]Where $j$ is the index of the first tower to the left of the last tower with a height less than or equal to $heights[i]$. We can use a monotonic stack to maintain this index.
We can use a similar method to find $g[i]$, which represents the height sum of the beautiful tower scheme from right to left with the $i$th tower as the tallest tower. The final answer is the maximum value of $f[i]+g[i]-heights[i]$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $maxHeights$.
-
class Solution { public long maximumSumOfHeights(List<Integer> maxHeights) { int n = maxHeights.size(); Deque<Integer> stk = new ArrayDeque<>(); int[] left = new int[n]; int[] right = new int[n]; Arrays.fill(left, -1); Arrays.fill(right, n); for (int i = 0; i < n; ++i) { int x = maxHeights.get(i); while (!stk.isEmpty() && maxHeights.get(stk.peek()) > x) { stk.pop(); } if (!stk.isEmpty()) { left[i] = stk.peek(); } stk.push(i); } stk.clear(); for (int i = n - 1; i >= 0; --i) { int x = maxHeights.get(i); while (!stk.isEmpty() && maxHeights.get(stk.peek()) >= x) { stk.pop(); } if (!stk.isEmpty()) { right[i] = stk.peek(); } stk.push(i); } long[] f = new long[n]; long[] g = new long[n]; for (int i = 0; i < n; ++i) { int x = maxHeights.get(i); if (i > 0 && x >= maxHeights.get(i - 1)) { f[i] = f[i - 1] + x; } else { int j = left[i]; f[i] = 1L * x * (i - j) + (j >= 0 ? f[j] : 0); } } for (int i = n - 1; i >= 0; --i) { int x = maxHeights.get(i); if (i < n - 1 && x >= maxHeights.get(i + 1)) { g[i] = g[i + 1] + x; } else { int j = right[i]; g[i] = 1L * x * (j - i) + (j < n ? g[j] : 0); } } long ans = 0; for (int i = 0; i < n; ++i) { ans = Math.max(ans, f[i] + g[i] - maxHeights.get(i)); } return ans; } } -
class Solution { public: long long maximumSumOfHeights(vector<int>& maxHeights) { int n = maxHeights.size(); stack<int> stk; vector<int> left(n, -1); vector<int> right(n, n); for (int i = 0; i < n; ++i) { int x = maxHeights[i]; while (!stk.empty() && maxHeights[stk.top()] > x) { stk.pop(); } if (!stk.empty()) { left[i] = stk.top(); } stk.push(i); } stk = stack<int>(); for (int i = n - 1; ~i; --i) { int x = maxHeights[i]; while (!stk.empty() && maxHeights[stk.top()] >= x) { stk.pop(); } if (!stk.empty()) { right[i] = stk.top(); } stk.push(i); } long long f[n], g[n]; for (int i = 0; i < n; ++i) { int x = maxHeights[i]; if (i && x >= maxHeights[i - 1]) { f[i] = f[i - 1] + x; } else { int j = left[i]; f[i] = 1LL * x * (i - j) + (j != -1 ? f[j] : 0); } } for (int i = n - 1; ~i; --i) { int x = maxHeights[i]; if (i < n - 1 && x >= maxHeights[i + 1]) { g[i] = g[i + 1] + x; } else { int j = right[i]; g[i] = 1LL * x * (j - i) + (j != n ? g[j] : 0); } } long long ans = 0; for (int i = 0; i < n; ++i) { ans = max(ans, f[i] + g[i] - maxHeights[i]); } return ans; } }; -
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)) -
func maximumSumOfHeights(maxHeights []int) (ans int64) { n := len(maxHeights) stk := []int{} left := make([]int, n) right := make([]int, n) for i := range left { left[i] = -1 right[i] = n } for i, x := range maxHeights { for len(stk) > 0 && maxHeights[stk[len(stk)-1]] > x { stk = stk[:len(stk)-1] } if len(stk) > 0 { left[i] = stk[len(stk)-1] } stk = append(stk, i) } stk = []int{} for i := n - 1; i >= 0; i-- { x := maxHeights[i] for len(stk) > 0 && maxHeights[stk[len(stk)-1]] >= x { stk = stk[:len(stk)-1] } if len(stk) > 0 { right[i] = stk[len(stk)-1] } stk = append(stk, i) } f := make([]int64, n) g := make([]int64, n) for i, x := range maxHeights { if i > 0 && x >= maxHeights[i-1] { f[i] = f[i-1] + int64(x) } else { j := left[i] f[i] = int64(x) * int64(i-j) if j != -1 { f[i] += f[j] } } } for i := n - 1; i >= 0; i-- { x := maxHeights[i] if i < n-1 && x >= maxHeights[i+1] { g[i] = g[i+1] + int64(x) } else { j := right[i] g[i] = int64(x) * int64(j-i) if j != n { g[i] += g[j] } } } for i, x := range maxHeights { ans = max(ans, f[i]+g[i]-int64(x)) } return } -
function maximumSumOfHeights(maxHeights: number[]): number { const n = maxHeights.length; const stk: number[] = []; const left: number[] = Array(n).fill(-1); const right: number[] = Array(n).fill(n); for (let i = 0; i < n; ++i) { const x = maxHeights[i]; while (stk.length && maxHeights[stk.at(-1)] > x) { stk.pop(); } if (stk.length) { left[i] = stk.at(-1); } stk.push(i); } stk.length = 0; for (let i = n - 1; ~i; --i) { const x = maxHeights[i]; while (stk.length && maxHeights[stk.at(-1)] >= x) { stk.pop(); } if (stk.length) { right[i] = stk.at(-1); } stk.push(i); } const f: number[] = Array(n).fill(0); const g: number[] = Array(n).fill(0); for (let i = 0; i < n; ++i) { const x = maxHeights[i]; if (i && x >= maxHeights[i - 1]) { f[i] = f[i - 1] + x; } else { const j = left[i]; f[i] = x * (i - j) + (j >= 0 ? f[j] : 0); } } for (let i = n - 1; ~i; --i) { const x = maxHeights[i]; if (i + 1 < n && x >= maxHeights[i + 1]) { g[i] = g[i + 1] + x; } else { const j = right[i]; g[i] = x * (j - i) + (j < n ? g[j] : 0); } } let ans = 0; for (let i = 0; i < n; ++i) { ans = Math.max(ans, f[i] + g[i] - maxHeights[i]); } return ans; }