Maximal range that each element is maximum in it

Array Stack Monotonic Stack

75.5% acceptance

Mar 31, 2026

You are given a 0-indexed array nums of distinct integers. Let us define a 0-indexed array ans of the same length as nums in the following way: ans[i] is the maximum length of a subarray nums[l..r], such that the maximum element in that subarray is equal to nums[i]. Return the array ans. Note that a subarray is a contiguous part of the array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_length_of_ranges(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let mut left = vec![0i32; n];
    let mut right = vec![0i32; n];
    let mut stack: Vec<usize> = Vec::new();
    for i in 0..n {
      while !stack.is_empty() && nums[*stack.last().unwrap()] < nums[i] {
        stack.pop();
      }
      left[i] = if stack.is_empty() { -1 } else { *stack.last().unwrap() as i32 };
      stack.push(i);
    }
    stack.clear();
    for i in (0..n).rev() {
      while !stack.is_empty() && nums[*stack.last().unwrap()] < nums[i] {
        stack.pop();
      }
      right[i] = if stack.is_empty() { n as i32 } else { *stack.last().unwrap() as i32 };
      stack.push(i);
    }
    (0..n).map(|i| right[i] - left[i] - 1).collect()
  }
}