Make array non decreasing

Array Stack Greedy Monotonic Stack

56.8% acceptance

Feb 25, 2026

You are given an integer array nums. In one operation, you can select a subarray and replace it with a single element equal to its maximum value. Return the maximum possible size of the array after performing zero or more operations such that the resulting array is non-decreasing.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_possible_size(nums: Vec<i32>) -> i32 {
    // Greedy: scan left to right. Maintain cur_max (max of current group).
    // Cut a group whenever cur_max >= prev_max.
    let mut prev_max = -1i32;
    let mut cur_max = -1i32;
    let mut count = 0i32;

    for &v in &nums {
      cur_max = cur_max.max(v);
      if cur_max >= prev_max {
        prev_max = cur_max;
        cur_max = -1;
        count += 1;
      }
    }

    count
  }
}