算法随笔_67: 使数组按非递减顺序排列

上一篇:算法随笔_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=0
        delCntLst=[0]*n
        for i in range(n-2, -1, -1):
            cnt=0
            while stck and nums[i]>nums[stck[-1]]:
                cnt+=1
                cnt=max(cnt,delCntLst[stck.pop()])
            delCntLst[i]=cnt
            res=max(res,cnt)
            stck.append(i)

        return res

关键词: 单调栈