<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>. In one step, <strong>remove</strong> all elements <code>nums[i]</code> where <code>nums[i - 1] &gt; nums[i]</code> for all <code>0 &lt; i &lt; nums.length</code>.</p>

<p>Return <em>the number of steps performed until </em><code>nums</code><em> becomes a <strong>non-decreasing</strong> array</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        # the ultimate result is a non-decreasing array
        # think: does that mean we just keep the non-decreasing sequence from original array?
        # also since the index 0 has no prev idx, always keep idx 0
        # question: even if we know the ultimate result, how to know number of steps?
        # [Not True]the number of turns needed to remove nums[i] = i-j for the closest j < i that nums[j]>nums[i]
        # => counterexample: [6,5,4,3,5] only needs 2 rounds, although the closest larger value to nums[4] is nums[0]
        # 3. Monotonic Stack + DP
        # dp[i] = number of rounds for nums[i] to completely eat whatever it can eat on the right of i
        # idea: when a larger num i comes in, drop all values in stack smaller than it, works because for later values that need a larger previous val to be removed, they can do it with i, don't need smaller and even further away values
        # e.g., the values in stack is [15,11,5] (in code stack store indexes)
        #and 13 comes in, we drop 5 and 11, stack becomes [15,13], 11 and 5 will not be useful for any later values
        # O(n)  O(n)
        dp = [0] * len(nums)   
        stack = []  #store indexes to a monotonic decreasing array
        for i, a in enumerate(nums):
            cur = 0
            # if stack[-1] is larger than a, only need 1 step to remove a
            while stack and nums[stack[-1]] <= a:
                # wait for all previous smaller val to be removed
                cur = max(cur, dp[stack.pop()])    
            if stack:   
                # i needs to be removed only if 
                #have a larger value to its left, 
                #i.e., when stack is not empty
                dp[i] = cur + 1
            stack.append(i)     # important

        return max(dp)

        # 2.[some cases not covered] My Approach: Monotonic Stack
        # idea: for each i that needs to be removed, 
        #if its prev is greater, only need 1 step, 
        #otherwise it needs to wait until all values between it and the greater prev are removed
        # use a stack to store the non-decreasing sequence
        # failed case: return 2 expected 3
        #[5,14,15,2,11,5,13,15], remove 2 and 5
        #[5,14,15,11,13,15], remove 11
        #[5,14,15,13,15], remove 13, 13 needs 3 steps, wait for 2 
        #[5,14,15,15]   
        # Problem of this approach: when loop to nums[4]=11, because it's greater than nums[5], I updated cur_wait to 0, however nums[6]=13 can't be removed when it's adjacent to nums[4]
        
        stack = [nums[0]]   # because nums[0] is always kept
        cur_wait = 0    # number of steps waited
        max_steps = 0
        for i in range(1, len(nums)): 
            print(i, cur_wait, stack)
            if nums[i] >= stack[-1]:    # keep nums[i]
                stack.append(nums[i])        
            else:   # remove nums[i]
                print("remove i", i, cur_wait + 1)
                max_steps = max(max_steps, cur_wait + 1)
                cur_wait += 1
            # refresh cur_wait, because later smaller ones only 
            #need to be adjacent to a larger value to be removed
            if i + 1 < len(nums) and nums[i] > nums[i + 1]:
                # if nums[i] is larger than nums[i+1], nums[i+1] doesn't need to wait for steps
                cur_wait = 0
        return max_steps


        # 1. [!TLE 79/87]Brute Force: Simulation
        # O(n^2): worst case each iteration only removes 1 value, at need to remove n-1 in total
        #e.g., [10,1,2,3,4,5], each step can only remove 1
        count = 0
        def onePass(nums):
            """
            return the resulted array
            """
            new_nums = []
            if not nums:
                return []
            new_nums.append(nums[0])
            for i in range(1, len(nums)):
                if nums[i] >= nums[i - 1]:
                    new_nums.append(nums[i])
            return new_nums

        while True:
            new_nums = onePass(nums)
            if len(new_nums) == len(nums):
                break
            count += 1
            nums = new_nums     #Important: update nums

        return count
689