Steps to make array non decreasing

Array Linked List Dynamic Programming Stack Monotonic Stack Simulation

24.6% acceptance

Feb 25, 2026

1407

149

You are given a 0-indexed integer array nums. In one step, remove all elements nums[i] where nums[i - 1] > nums[i] for all 0 < i < nums.length. Return the number of steps performed until nums becomes a non-decreasing array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn total_steps(nums: Vec<i32>) -> i32 {
    // dp[i] = the step at which nums[i] gets removed (0 means never removed)
    // Building dp using monotone decreasing stack, right-to-left
    // When we see nums[i], find first position j > i where nums[j] < nums[i].
    // dp[i] = 1 + dp[j], dp[j] = 1 + dp[next smaller after j], etc.
    // Use stack: maintain decreasing elements to the RIGHT
    let n = nums.len();
    let mut dp = vec![0i32; n];
    // Process right to left with a monotone stack
    // stack stores indices in decreasing value order
    let mut stack: Vec<usize> = Vec::new();
    for i in (0..n).rev() {
      // Find dp[i]: how many steps until i is consumed
      // i can consume elements to its right that are smaller
      let mut steps = 0;
      while let Some(&top) = stack.last() {
        if nums[top] < nums[i] {
          // nums[top] is dominated by nums[i]
          // dp[top] is how long it takes nums[i] to be adjacent to something > nums[top]
          // actually dp[top] should already be set
          steps = (steps + 1).max(dp[top]);
          stack.pop();
        } else {
          break;
        }
      }
      dp[i] = steps;
      stack.push(i);
    }
    *dp.iter().max().unwrap_or(&0)
  }
}