Problem

You are given an array heights of n integers representing the number of bricks in n consecutive towers. Your task is to remove some bricks to form a mountain-shaped tower arrangement. In this arrangement, the tower heights are non-decreasing, reaching a maximum peak value with one or multiple consecutive towers and then non-increasing.

Return the maximum possible sum of heights of a mountain-shaped tower arrangement.

Examples

Example 1

1
2
3
4

Input: heights = [5,3,4,1,1]
Output: 13
Explanation:
We remove some bricks to make `heights = [5,3,3,1,1]`, the peak is at index 0.

Example 2

1
2
3
4

Input: heights = [6,5,3,9,2,7]
Output: 22
Explanation:
We remove some bricks to make `heights = [3,3,3,9,2,2]`, the peak is at index 3.

Example 3

1
2
3
4

Input: heights = [3,2,5,5,2,3]
Output: 18
Explanation:
We remove some bricks to make `heights = [2,2,5,5,2,2]`, the peak is at index 2 or 3.

Constraints

  • 1 <= n == heights.length <= 10^3
  • 1 <= heights[i] <= 10^9

Solution

Method 1 – Monotonic Stack for Left and Right Limits

Intuition

To maximize the sum while forming a mountain, for each possible peak, we want to keep the tallest possible towers to the left and right, but never exceeding the peak. We use monotonic stacks to efficiently compute the maximum sum for each peak.

Approach

  1. For each index, compute the maximum sum to the left (including itself) where heights are non-increasing towards the peak.
  2. Similarly, compute the maximum sum to the right.
  3. For each index, the total sum is left sum + right sum - heights[i] (since the peak is counted twice).
  4. Return the maximum total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    long long maximumSumOfHeights(vector<int>& h) {
        int n = h.size();
        vector<long long> left(n), right(n);
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && h[st.top()] > h[i]) st.pop();
            if (st.empty()) left[i] = 1LL * h[i] * (i + 1);
            else left[i] = left[st.top()] + 1LL * h[i] * (i - st.top());
            st.push(i);
        }
        while (!st.empty()) st.pop();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && h[st.top()] > h[i]) st.pop();
            if (st.empty()) right[i] = 1LL * h[i] * (n - i);
            else right[i] = right[st.top()] + 1LL * h[i] * (st.top() - i);
            st.push(i);
        }
        long long ans = 0;
        for (int i = 0; i < n; ++i) ans = max(ans, left[i] + right[i] - h[i]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func maximumSumOfHeights(h []int) int64 {
    n := len(h)
    left := make([]int64, n)
    right := make([]int64, n)
    st := []int{}
    for i := 0; i < n; i++ {
        for len(st) > 0 && h[st[len(st)-1]] > h[i] {
            st = st[:len(st)-1]
        }
        if len(st) == 0 {
            left[i] = int64(h[i]) * int64(i+1)
        } else {
            left[i] = left[st[len(st)-1]] + int64(h[i])*int64(i-st[len(st)-1])
        }
        st = append(st, i)
    }
    st = []int{}
    for i := n - 1; i >= 0; i-- {
        for len(st) > 0 && h[st[len(st)-1]] > h[i] {
            st = st[:len(st)-1]
        }
        if len(st) == 0 {
            right[i] = int64(h[i]) * int64(n-i)
        } else {
            right[i] = right[st[len(st)-1]] + int64(h[i])*int64(st[len(st)-1]-i)
        }
        st = append(st, i)
    }
    ans := int64(0)
    for i := 0; i < n; i++ {
        if left[i]+right[i]-int64(h[i]) > ans {
            ans = left[i] + right[i] - int64(h[i])
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public long maximumSumOfHeights(int[] h) {
        int n = h.length;
        long[] left = new long[n], right = new long[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            while (!st.isEmpty() && h[st.peek()] > h[i]) st.pop();
            if (st.isEmpty()) left[i] = 1L * h[i] * (i + 1);
            else left[i] = left[st.peek()] + 1L * h[i] * (i - st.peek());
            st.push(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.isEmpty() && h[st.peek()] > h[i]) st.pop();
            if (st.isEmpty()) right[i] = 1L * h[i] * (n - i);
            else right[i] = right[st.peek()] + 1L * h[i] * (st.peek() - i);
            st.push(i);
        }
        long ans = 0;
        for (int i = 0; i < n; ++i) ans = Math.max(ans, left[i] + right[i] - h[i]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun maximumSumOfHeights(h: IntArray): Long {
        val n = h.size
        val left = LongArray(n)
        val right = LongArray(n)
        val st = ArrayDeque<Int>()
        for (i in 0 until n) {
            while (st.isNotEmpty() && h[st.last()] > h[i]) st.removeLast()
            if (st.isEmpty()) left[i] = h[i].toLong() * (i + 1)
            else left[i] = left[st.last()] + h[i].toLong() * (i - st.last())
            st.addLast(i)
        }
        st.clear()
        for (i in n - 1 downTo 0) {
            while (st.isNotEmpty() && h[st.last()] > h[i]) st.removeLast()
            if (st.isEmpty()) right[i] = h[i].toLong() * (n - i)
            else right[i] = right[st.last()] + h[i].toLong() * (st.last() - i)
            st.addLast(i)
        }
        var ans = 0L
        for (i in 0 until n) ans = maxOf(ans, left[i] + right[i] - h[i])
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def maximumSumOfHeights(self, h: list[int]) -> int:
        n = len(h)
        left = [0]*n
        right = [0]*n
        st = []
        for i in range(n):
            while st and h[st[-1]] > h[i]:
                st.pop()
            if not st:
                left[i] = h[i]*(i+1)
            else:
                left[i] = left[st[-1]] + h[i]*(i-st[-1])
            st.append(i)
        st.clear()
        for i in range(n-1, -1, -1):
            while st and h[st[-1]] > h[i]:
                st.pop()
            if not st:
                right[i] = h[i]*(n-i)
            else:
                right[i] = right[st[-1]] + h[i]*(st[-1]-i)
            st.append(i)
        ans = 0
        for i in range(n):
            ans = max(ans, left[i]+right[i]-h[i])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

impl Solution {
    pub fn maximum_sum_of_heights(h: Vec<i32>) -> i64 {
        let n = h.len();
        let mut left = vec![0i64; n];
        let mut right = vec![0i64; n];
        let mut st = Vec::new();
        for i in 0..n {
            while let Some(&top) = st.last() {
                if h[top] > h[i] { st.pop(); } else { break; }
            }
            if st.is_empty() {
                left[i] = h[i] as i64 * (i as i64 + 1);
            } else {
                left[i] = left[*st.last().unwrap()] + h[i] as i64 * (i as i64 - *st.last().unwrap() as i64);
            }
            st.push(i);
        }
        st.clear();
        for i in (0..n).rev() {
            while let Some(&top) = st.last() {
                if h[top] > h[i] { st.pop(); } else { break; }
            }
            if st.is_empty() {
                right[i] = h[i] as i64 * (n as i64 - i as i64);
            } else {
                right[i] = right[*st.last().unwrap()] + h[i] as i64 * (*st.last().unwrap() as i64 - i as i64);
            }
            st.push(i);
        }
        let mut ans = 0i64;
        for i in 0..n {
            ans = ans.max(left[i] + right[i] - h[i] as i64);
        }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each index is pushed and popped at most once from the stack.
  • 🧺 Space complexity: O(n) — For the left and right sum arrays.