2289. Steps to Make Array Non-decreasing Medium

1/**
2 * [2289] Steps to Make Array Non-decreasing
3 *
4 * 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.
5 * Return the number of steps performed until nums becomes a non-decreasing array.
6 *  
7 * Example 1:
8 * 
9 * Input: nums = [5,3,4,4,7,3,6,11,8,5,11]
10 * Output: 3
11 * Explanation: The following are the steps performed:
12 * - Step 1: [5,<u>3</u>,4,4,7,<u>3</u>,6,11,<u>8</u>,<u>5</u>,11] becomes [5,4,4,7,6,11,11]
13 * - Step 2: [5,<u>4</u>,4,7,<u>6</u>,11,11] becomes [5,4,7,11,11]
14 * - Step 3: [5,<u>4</u>,7,11,11] becomes [5,7,11,11]
15 * [5,7,11,11] is a non-decreasing array. Therefore, we return 3.
16 * 
17 * Example 2:
18 * 
19 * Input: nums = [4,5,7,7,13]
20 * Output: 0
21 * Explanation: nums is already a non-decreasing array. Therefore, we return 0.
22 * 
23 *  
24 * Constraints:
25 * 
26 * 1 <= nums.length <= 10^5
27 * 1 <= nums[i] <= 10^9
28 * 
29 */
30pub struct Solution {}
31
32// problem: https://leetcode.com/problems/steps-to-make-array-non-decreasing/
33// discuss: https://leetcode.com/problems/steps-to-make-array-non-decreasing/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36use std::cmp;
37impl Solution {
38    pub fn total_steps(nums: Vec<i32>) -> i32 {
39        let mut result = 0;
40        let mut stack: Vec<(i32, i32)> = vec![];
41        for i in nums.iter().rev() {
42            if stack.is_empty() {
43                stack.push((*i, 0));
44            } else {
45                let mut current = 0;
46                while stack.last().is_some() && stack.last().unwrap().0 < *i {
47                    let l = stack.pop().unwrap();
48                    current = cmp::max(current + 1, l.1);
49                }
50                result = cmp::max(current, result);
51                stack.push((*i, current));
52            }
53        }
54        result
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_2289() {
66        assert_eq!(Solution::total_steps(vec![5,3,4,4,7,3,6,11,8,5,11]), 3);
67    }
68}
69