Beautiful towers ii

Array Stack Monotonic Stack

36.2% acceptance

Feb 25, 2026

475

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] heights is 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_sum_of_heights(max_heights: Vec<i32>) -> i64 {
    let n = max_heights.len();
    // For each peak, use monotone stack to compute prefix/suffix sums efficiently
    // left[i] = sum of heights on [0..=i] when i is peak (non-increasing going left)
    // right[i] = sum of heights on [i..n-1] when i is peak (non-increasing going right)
    let h = &max_heights;
    let mut left = vec![0i64; n];
    let mut stack: Vec<usize> = vec![];
    // left[i] = left[prev_smaller] + h[i] * (i - prev_smaller)
    for i in 0..n {
      while !stack.is_empty() && h[*stack.last().unwrap()] >= h[i] {
        stack.pop();
      }
      if stack.is_empty() {
        left[i] = h[i] as i64 * (i + 1) as i64;
      } else {
        let j = *stack.last().unwrap();
        left[i] = left[j] + h[i] as i64 * (i - j) as i64;
      }
      stack.push(i);
    }
    let mut right = vec![0i64; n];
    stack.clear();
    for i in (0..n).rev() {
      while !stack.is_empty() && h[*stack.last().unwrap()] >= h[i] {
        stack.pop();
      }
      if stack.is_empty() {
        right[i] = h[i] as i64 * (n - i) as i64;
      } else {
        let j = *stack.last().unwrap();
        right[i] = right[j] + h[i] as i64 * (j - i) as i64;
      }
      stack.push(i);
    }
    (0..n).map(|i| left[i] + right[i] - h[i] as i64).max().unwrap_or(0)
  }
}