使数组按非递减顺序排列

Posted on | Post modified:

Leetcode 6080. 使数组按非递减顺序排列

题面

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。

重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。

题解

  • 对于$nums[i]$，如果存在$j$满足$j < i$ 且$nums[j] < nums[i]$，则$nums[i]$则一定会被删除

  • 对于$nums[i]$，找到左边距离其最近的$nums[j]$，则在删除$nums[i]$之前，一定是先删除了$[nums[j + 1],…, nums[i - 1]]$之后再删除的$nums[i]$

  • 令$dp[i]$表示删除$nums[i]$的轮数，则有:

  • 因此我们可以用单调栈维护一个单调递减的栈，对于每个$i$求得对应的$j$，并且在维护单调栈的过程中进行动态规划，时间复杂度$O(n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int totalSteps(vector<int>& nums) {
        int n = (int)nums.size();
        vector<int> dp(n, 0);
        stack<int> sta;
        int maxx = 0;
        for(int i = 0; i < n; i++){
            int cur = 0;
            while(!sta.empty() && nums[sta.top()] <= nums[i]){
                cur = max(cur, dp[sta.top()]);
                sta.pop();
            }
            if(!sta.empty()){//说明存在nums[j] < nums[i]
                dp[i] = cur + 1;
            }
            maxx = max(maxx, dp[i]);
            sta.push(i);
        }
        return maxx;
    }
};