LeetCode6080 使数组按非递减顺序排列

发表于 | 分类于 |
字数统计: 580 | 阅读时长 ≈ 2

链接: https://leetcode.cn/problems/steps-to-make-array-non-decreasing/

题意

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。
重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。

解法

周赛第三题 卡了好久
比赛的时候想到了要用单调栈这一类的解法来写
但是终归是没有能够调出来
这是一道比较接近思维的题
要求删除次数，首先考虑的是统计每个数右边比当前数小的数字个数
但是这样的时间复杂度来到了N^2
考虑使用单调栈进行优化
元素 x 会被左边某个比他大的元素 y 给移除（如果存在的话）。
我们需要计算在移除 x 之前，移除了多少个比 y 小的元素，从而算出移除 x 的时刻（第几步操作）。
答案可以转换成所有元素被移除的时刻的最大值。
对于一个新的数字x，判断当前数是否比栈顶的数要小
如果是的话，那当前数一定在其被删除以后才删除
所以用上一个数的maxT来对其赋值
最后取到这所有栈中数的maxT
然后再判断一下当前栈的情况
由于维护了一个单调递减的栈，所以如果栈空，则说明当前数不用被删除
否则当前数需要被删 maxT加1 加入栈中
在这个过程中最大的maxT即为答案

代码

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) {
        vector<pair<int, int>> vp;
        int ans = 0;
        for (int i: nums) {
            int maxT = 0;
            while(vp.size() && vp.back().first <= i) {
                //左边小于等于num的值都需要在num被删除之前删掉,此时maxT 为删掉左边这些小与等于num的数的最大时间
                maxT = max(maxT, vp.back().second);
                vp.pop_back();
            }
            if (vp.size()) {
                 //如果stack 不为空,所有还有左边还有比num值大的情况，表示num需要被删除，如果为空，说明num不用删除
                maxT++;
            }
            vp.push_back({i, maxT});
            ans = max(ans, maxT);
        }
        return ans;
    }
};