Problem

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 untilnums becomes anon-decreasing array.

Examples

Example 1

1
2
3
4
5
6
7

Input: nums = [5,3,4,4,7,3,6,11,8,5,11]
Output: 3
Explanation: The following are the steps performed:
- Step 1: [5,**_3_** ,4,4,7,_**3**_ ,6,11,_**8**_ ,_**5**_ ,11] becomes [5,4,4,7,6,11,11]
- Step 2: [5,_**4**_ ,4,7,_**6**_ ,11,11] becomes [5,4,7,11,11]
- Step 3: [5,_**4**_ ,7,11,11] becomes [5,7,11,11]
[5,7,11,11] is a non-decreasing array. Therefore, we return 3.

Example 2

1
2
3

Input: nums = [4,5,7,7,13]
Output: 0
Explanation: nums is already a non-decreasing array. Therefore, we return 0.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Reverse Monotonic Stack

Intuition

Let’s build the solution from scratch by walking through examples:

Consider nums = [10, 4, 5, 6].

  • Going left to right, 10 > 4, so 4 is removed in round 1.
  • 10 > 5, so 5 is removed in round 2.
  • 10 > 6, so 6 is removed in round 3.

But this doesn’t always work for all cases. For example, nums = [10, 4, 5, 6, 3, 4]:

  • If we go left to right, we might overcount rounds. Instead, we need to process from right to left.
  • When we reach 6, it removes both 3 and 4 in 2 rounds.
  • When we reach 10, it removes 6 (which already removed 3 and 4 in 2 rounds), so the total rounds for 10 should be 2, not 1. When 10 removes 8, we do round + 1, i.e., 2+1 = 3.

This shows that for each element, the number of rounds is determined by the maximum rounds among the elements it removes, plus one. We use a stack to track this efficiently.

Approach

  1. Start from the rightmost element and move left.
  2. Use a stack to store pairs (value, rounds).
  3. For each element:
    • Pop all elements from the stack that are smaller, updating the rounds as max(cnt+1, popped_rounds).
    • Update the result with the maximum rounds seen so far.
    • Push the current element and its rounds onto the stack.
  4. Return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        stack<pair<int, int>> stk;
        int res = 0;
        for (int i = nums.size() - 1; i >= 0; --i) {
            int cnt = 0;
            while (!stk.empty() && nums[i] > stk.top().first) {
                cnt = max(cnt + 1, stk.top().second);
                stk.pop();
            }
            res = max(res, cnt);
            stk.push({nums[i], cnt});
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int totalSteps(int[] nums) {
        Deque<int[]> stack = new ArrayDeque<>(); // [value, rounds]
        int res = 0;
        for (int i = nums.length - 1; i >= 0; --i) {
            int cnt = 0;
            while (!stack.isEmpty() && nums[i] > stack.peek()[0]) {
                cnt = Math.max(cnt + 1, stack.pop()[1]);
            }
            res = Math.max(res, cnt);
            stack.push(new int[]{nums[i], cnt});
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def totalSteps(self, nums: list[int]) -> int:
        stack = []  # (value, rounds)
        res = 0
        for i in range(len(nums) - 1, -1, -1):
            cnt = 0
            while stack and nums[i] > stack[-1][0]:
                cnt = max(cnt + 1, stack.pop()[1])
            res = max(res, cnt)
            stack.append((nums[i], cnt))
        return res

Complexity

  • ⏰ Time complexity: O(n), each element is pushed and popped at most once.
  • 🧺 Space complexity: O(n), for the stack.