上一篇:算法随笔_66: 多数元素_方法2-CSDN博客
=====
题目描述如下:
给你一个下标从 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 。
=====
算法思路:
首先，我们从右往左观察原数组，发现其中蕴含着递推关系。我们设如下变量:
n为原数组长度。
数组cntLst: cntLst[i]表示区间[i, n-1]变为非递减数组所需的操作数。
数组delCntLst: delCntLst[i]表示元素i在碰到比它大的元素之前需要做多少次的消除操作。
那么递推关系就是，cntLst[i]=max(delCntLst[i], cntLst[i+1])
假如cntLst[i+1]用了10次操作，无论在这段区间[i+1, n-1]如何消除的元素，如果delCntLst[i]用了15次的操作，那它的前10次是可以随着cntLst[i+1]的操作同时完成的，因此cntLst[i]就用了15次。
同理，如果delCntLst[i]用了5次的操作，那cntLst[i+1]的前5次是可以随着delCntLst[i]的操作同时完成的，因此cntLst[i]总共就用了10次。
我们再来看delCntLst[i]是如何计算的。我们设cnt为元素i当前消除的操作数，初始值为0。元素i每消除一个它后面比它小的元素，操作数cnt都加1，然后再取max(cnt, delCntLst[i+1])。原理和上面的类似。要取操作数大的那个值。因为少的操作数可以和多的操作数的部分操作同时进行。
最后在算法具体实现时，我们可以使用一个单调栈stck来维护元素的消除和添加。当我们从右往左遍历原数组时，只要当前的元素大于栈顶元素，即nums[i]>stck[-1]，我们就弹出栈顶，不断判断，直到当前元素nums[i]小于等于栈顶，我们才把nums[i]放入栈。然后我们再更新delCntLst和cntLst。
代码实现时，cntLst数组可以不要，只需要一个变量res即可，具体可参考下面的Python代码。此算法的时间复杂度为O(n)。
class Solution(object):def totalSteps(self, nums):""":type nums: List[int]:rtype: int"""n=len(nums)stck=[n-1]res=0delCntLst=[0]*nfor i in range(n-2, -1, -1):cnt=0while stck and nums[i]>nums[stck[-1]]:cnt+=1cnt=max(cnt,delCntLst[stck.pop()])delCntLst[i]=cntres=max(res,cnt)stck.append(i)return res关键词: 单调栈
