难度: Medium
给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。
重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。
示例 1：
输入：nums = [5,3,4,4,7,3,6,11,8,5,11] 输出：3 解释：执行下述几个步骤： - 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11] - 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11] - 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11] [5,7,11,11] 是一个非递减数组，因此，返回 3 。
示例 2：
输入：nums = [4,5,7,7,13] 输出：0 解释：nums 已经是一个非递减数组，因此，返回 0 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109运行时间: 158 ms
内存: 30.1 MB
class Solution:
def totalSteps(self, nums: List[int]) -> int:
stk = []
ans, n = 0, len(nums)
dp = [0] * n
for i in range(n - 1, -1, -1):
while stk and nums[i] > nums[stk[-1]]:
dp[i] = max(dp[i] + 1, dp[stk.pop()])
stk.append(i)
return max(dp)
该题解采用了单调栈和动态规划的结合方式。首先，初始化一个空栈和一个动态规划数组dp，dp[i]用于记录以nums[i]为起点，数组需要经过的删除步骤数。从数组的末尾开始向前遍历，对于每个元素nums[i]，检查栈顶元素representing the indices of elements in the array。如果栈不为空且nums[i]大于栈顶元素对应的数组值，说明nums[i]能在一次操作中保留下来而栈顶元素会被删除，此时将栈顶元素出栈，并更新dp[i]为max(dp[i] + 1, dp[栈顶元素])，意味着nums[i]能延续的删除步骤至少是之前的步骤加一或者栈顶元素的步骤。将每个元素的索引最终压入栈中。最后，返回dp数组中的最大值，即为整个数组变为非递减数组所需的最大删除步骤数。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def totalSteps(self, nums: List[int]) -> int:
stk = [] # Initialize a stack
ans, n = 0, len(nums)
dp = [0] * n # dp array to store the steps needed to make subarray non-decreasing
for i in range(n - 1, -1, -1): # Start from the end of the array
while stk and nums[i] > nums[stk[-1]]: # While stack is not empty and current element is bigger than the top of the stack
dp[i] = max(dp[i] + 1, dp[stk.pop()]) # Calculate the max steps needed
stk.append(i) # Push current index onto the stack
return max(dp) # Return the maximum value from dp array, which gives the total steps needed
单调栈的特点是能够在O(1)的时间复杂度内访问到需要比较的元素，并且能够在O(1)的时间复杂度内添加和删除元素。在本算法中，需要频繁地进行元素比较和删除操作，单调栈可以高效地处理这些操作，保证整体算法的效率。相比之下，如果使用数组或链表，虽然也可以实现相同的功能，但在删除元素时可能需要更高的时间复杂度，特别是数组在删除元素后还需要处理元素的移动，效率较低。
动态规划数组dp用于记录每个位置i所需的最小删除步骤数，使得从该位置到数组末尾的子数组成为非递减序列。初始化所有元素的值为0是因为每个元素本身不需要任何删除操作就可以作为长度为1的非递减序列，即在最初的情况下，没有需要删除的其他元素，所以初始步骤数为0。
这个条件用于检查当前元素nums[i]是否大于栈顶元素对应的数组值。如果是，这意味着为了保持非递减序列，栈顶元素（较小的元素）需要被删除，因为它位于当前元素（较大的元素）之后。通过这种方式，算法逐步从数组末尾向前确保任何时刻栈内的元素对应的数组值都是非递减的。每次循环检查和可能的删除操作都是为了维持这个非递减的性质。
这里的更新逻辑是为了确保dp[i]记录的是以nums[i]为起点所需的最大删除步骤数。当nums[i]大于栈顶元素时，栈顶元素需要被删除，此时dp[i]应至少为栈顶元素的dp值加1（表示除了栈顶元素外还可能需要更多的删除步骤）。使用max函数是为了处理可能的多个栈顶元素被连续删除的情况，确保dp[i]始终是正确的最大步骤数。