<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>

# Right off the bat seems like a stack problem -> should practice monotonic stacks
# I don't think you actually even need a stack -> just the top number
#if nums[i] < cur_max:
#                if nums[i] >= nums[i - 1]:
# If you put the inner condition with the first and then join it with a "and", it can trigger the else and reset everything. So becareful of combining statements, always look to the next one or see if the next one gets affected!

# Maybe keep track of the decreasing streaks because every decreasing streak = +1, just with how the problem is stated

# Idea is that when you have a bunch of mountains, you have really two sets of mountains, the first set which is the "local" mountain and the mountain formed from the peaks

# When you have a classic V, you know that the dipping point gets removed but not the right upper part because that's in step 2...
# Monotonic Increasing Stack

# Basically you pop off every number that you are "greater" than because that's exactly what is in the problem statement

# The exact problem is that 
# - The removals are done in steps
# - There can be many new mountains that form after you deal with one mountain [5,14,15,2,11,5,13,15], new mountain is 15 11 13 after you remove the little ones in between

# VVVV

# [5,14,15,2,11,5,13,15] -> [15 2 11 5 13] -> resolving the 2 and the 5 creates another wave [15 11 13]
# [10,1,2,3,4,5,6,1,2,3]
#
# dp[i] states that to get to the ith number, you had to get through dp[i] steps
# if dp[i + 1] > dp[i], then it took more steps for the number in front (and assuming your number is greater) so that means you have to "eat" that number in front anyway but let's say it took 2 steps to eat the number in front and 7 steps for that number to eat everything in its front -> then imagine at the 2nd step you have x y z z z z z, so you synchronize so that's why you take the 7 steps at dp[i]

# Understanding dp[i] = max(dp[st[-1]], dp[i + 1]) -> dp[i + 1] makes sense because if the number in front of you is smaller, you need to "eat" it so you do a +1. The reason why you do dp[i + 1] is because you already do a +1 from that number and you may have eaten previous numbers beforehand. Like let's say you had 10 9 8 9 8 7 -> 10 9 (you ate 2) but you need to eat the 9 so it's a +1

# The problem is really about measuring waves and then also how do I put that in terms of data structures? DP array really shows the "compounding" waves
class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        st = []
        
        for i in range(len(nums) - 1, -1, -1):
            while st and nums[st[-1]] < nums[i]:
                dp[i] = max(dp[st.pop()], dp[i] + 1)
            st.append(i)
            
        return max(dp)
            
            
677