Maximum width ramp

Array Two Pointers Stack Monotonic Stack

55.8% acceptance

Feb 25, 2026

2840

A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i. Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_width_ramp(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    // Build decreasing monotonic stack of indices
    let mut stack: Vec<usize> = Vec::new();
    for i in 0..n {
      if stack.is_empty() || nums[*stack.last().unwrap()] > nums[i] {
        stack.push(i);
      }
    }
    let mut ans = 0i32;
    for j in (0..n).rev() {
      while !stack.is_empty() && nums[*stack.last().unwrap()] <= nums[j] {
        ans = ans.max(j as i32 - *stack.last().unwrap() as i32);
        stack.pop();
      }
    }
    ans
  }
}