[LeetCode解题报告] 2289. 使数组按非递减顺序排列

[LeetCode解题报告] 2289. 使数组按非递减顺序排列

• • 一、 题目
  • • 1. 题目描述
    • 2. 原题链接
  • 二、 解题报告
  • • 1. 思路分析
    • 2. 复杂度分析
    • 3. 代码实现
  • 三、 本题小结
  • 四、 参考链接

一、 题目 1. 题目描述

给你一个下标从 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 <= 105
• 1 <= nums[i] <= 109

Related Topics

• 栈
• 数组
• 链表
• 单调栈

• 👍 63
• 👎 0

2. 原题链接

链接: 2289. 使数组按非递减顺序排列

二、 解题报告 1. 思路分析

这题是20220529力扣周赛第三题，把我直接卡住，连第四题那么简单都没做。
当时隐约有单调栈的思路，但最终没想明白。
想了一周终于做出来啦！

从题意可以得出：

1. 每个数只要前边有比它大的数，一定会被删除。

2. 每个数都会被他前边更大的数删除，但不一定是最近那个，因为那个数可能会被自己前边的大数删掉。
   如[5,4,1,2], 2这个数不会被4删掉，因为4会被5删掉。
   但这没关系，这相当于5代替了4的位置。

3. 因此每个数被删除的时间只取决于它前边比它小的数能挡几轮。
   换言之,我们设dp[i]为第i个数第几轮被删除,显然答案就是max(dp),
   那么状态转移方程为:

   • dp[i] = max{dp[j] + 1 | k
   • 显然k可以通过单调递减栈以*O(n)*的时间算出来，计算left[i]。
   • 发现这个dp过程是*O(n²)*的，数据规模是10^5，过不了。
   • 已经提交试过了，TLE。

4. 下面开始讨论如何优化这个dp，从O(n²)到O(n):

   • 我们发现步骤3.1中，每个j的范围是(k,i)，左开右开区间，k为i左边第一个比它大的数，这正好是单调栈构建的过程。
   • 也就是说，每个j都是在单调栈i入栈时，被pop的数，那么我们可以再这一步同时计算dp[i]。
   • 那么是否存在dp[i]因更前方的pop而漏算的情况呢？
   • [7,2,1,5,3,4,6],观察这个案例,5的删除次数只取决于1,2的删除次数max+1。
     • 而6这个数，按步骤3.1的推算应该计算1,2,5,3,4每个数的次数max+1，
     • 实际上 dp[5] = max(dp[1,2]+1)，因此不需要计算前边1，2,只需要计算5以及以后的数，即5,3,4，
     • 这三个数恰好是构造单调栈时，入栈6时需要pop的数。
     • 因此不存在漏算。
   • 特别的，每个数i若入栈前把栈删空了，说明这个数i前边没有比它更大的数，他不会被删除，dp[i] = 0

5. 空间优化：由于每次计算只依赖于栈中pop的数，因此不需要存所有dp[i],只需要存栈中留着的即可。快一半。

6. 后来去题解抄了一个逆序版本的单调栈，更快，但我没看懂。
   

2. 复杂度分析

最坏时间复杂度O(n)

3. 代码实现

单调递减栈DP。

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        """
        1.每个数只要前边有比它大的数，一定会被删除。
        2.每个数都会被他前边更大的数删除，但不一定是最近那个，因为那个数可能会被自己前边的大数删掉
          如[5,4,1,2], 2这个数不会被4删掉，因为4会被5删掉。
          但这没关系，这相当于5代替了4的位置。
        3.因此每个数被删除的时间只取决于它前边比它小的数能挡几轮：
        4.换言之：每个数被删除的时间dp[i]=max{dp[j]+1|k
        n = len(nums)
        # left = [-1]*n  # left[i]是i左边第一个比它大的数的下标
        stack = []
        dp=[0]*n
        for i in range(n):
            if i > 0 and nums[i] < nums[i-1]:
                dp[i] = 1
            while stack and nums[stack[-1]] <= nums[i]:  # 构造单调递减栈，需要把栈顶比本数小的数都干掉
                dp[i] = max(dp[i],dp[stack[-1]]+1)
                stack.pop()           
            if not stack:
                dp[i] = 0 
            # if stack :
            #     left[i] = stack[-1]
            stack.append(i)
        # print(dp)
        # print(left)
        # 以下O(n^2),TLE
        # for i in range(0,n):
        #     l = left[i]
        #     if l == -1:
        #         dp[i] = 0
        #     else:
        #         dp[i] = 1
        #         for j in range(l+1,i):
        #             dp[i] = max(dp[i],dp[j]+1)        

        return max(dp)

单调递减栈DP+空间优化。

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        ans = 0
        stack = []  # stack[i] = (a,b) ，a是i前边的下标，b是下标a的删除次数 
        for i in range(len(nums)):
            cnt = 1
            while stack and nums[stack[-1][0]] <= nums[i]:  # 构造单调递减栈，需要把栈顶比本数小的数都干掉
                cnt = max(cnt,stack.pop()[1]+1)                         
            if not stack:
                cnt = 0
            ans = max(ans,cnt)
            stack.append((i,cnt))  
        return ans

抄的逆序+单调递减栈

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        s = []
        for a in nums[::-1]:
            cnt = 0
            while s and s[-1][0] < a:
                cnt = max(cnt + 1, s.pop()[1])
            s.append([a, cnt])
        return max(cnt for _, cnt in s)

三、 本题小结

1. 这题是单调递减栈的变相应用。

四、 参考链接

• 链接: [python刷题模板] 单调栈