Beautiful towers i

Array Stack Monotonic Stack

44.3% acceptance

Feb 25, 2026

363

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_sum_of_heights(heights: Vec<i32>) -> i64 {
    let n = heights.len();
    // Try each peak index
    let mut ans = 0i64;
    for peak in 0..n {
      let mut sum = heights[peak] as i64;
      // left side: non-increasing from peak going left
      let mut h = heights[peak];
      for i in (0..peak).rev() {
        h = h.min(heights[i]);
        sum += h as i64;
      }
      // right side: non-increasing from peak going right
      h = heights[peak];
      for i in (peak+1)..n {
        h = h.min(heights[i]);
        sum += h as i64;
      }
      ans = ans.max(sum);
    }
    ans
  }
}