跳转至

3818. 移除前缀使数组严格递增

题目描述

给你一个整数数组 nums。

你需要从 nums 中 恰好 移除一个前缀（可以为空）。

返回一个整数，表示被移除的前缀的 最小 长度，使得剩余的数组 严格递增 。

数组的 前缀 是从数组的起始位置开始，一直延伸到任意位置的子数组。

如果一个数组的每个元素都严格大于它的前一个元素（若存在），则称该数组 严格递增 。

 

示例 1：

输入： nums = [1,-1,2,3,3,4,5]

输出： 4

解释：

移除前缀 prefix = [1, -1, 2, 3] 后，剩余数组为 [3, 4, 5]，严格递增。

示例 2：

输入： nums = [4,3,-2,-5]

输出： 3

解释：

移除前缀 prefix = [4, 3, -2] 后，剩余数组为 [-5]，严格递增。

示例 3：

输入： nums = [1,2,3,4]

输出： 0

解释：

数组 nums = [1, 2, 3, 4] 已经是严格递增的，因此移除空前缀即可。

 

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109​​​​​​​

解法

方法一：倒序遍历

我们可以从数组的末尾开始往前遍历，找到第一个不满足严格递增条件的位置 \(i\)，即满足 \(nums[i-1] \geq nums[i]\) 的位置。此时，移除前缀的最小长度即为 \(i\)。

如果整个数组都是严格递增的，那么我们不需要移除任何前缀，返回 \(0\) 即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组的长度。空间复杂度 \(O(1)\)。

1
2
3
4
5
6
class Solution:
    def minimumPrefixLength(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1, 0, -1):
            if nums[i - 1] >= nums[i]:
                return i
        return 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int minimumPrefixLength(int[] nums) {
        for (int i = nums.length - 1; i > 0; --i) {
            if (nums[i - 1] >= nums[i]) {
                return i;
            }
        }
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int minimumPrefixLength(vector<int>& nums) {
        for (int i = nums.size() - 1; i; --i) {
            if (nums[i - 1] >= nums[i]) {
                return i;
            }
        }
        return 0;
    }
};

1
2
3
4
5
6
7
8
func minimumPrefixLength(nums []int) int {
    for i := len(nums) - 1; i > 0; i-- {
        if nums[i-1] >= nums[i] {
            return i
        }
    }
    return 0
}

1
2
3
4
5
6
7
8
function minimumPrefixLength(nums: number[]): number {
    for (let i = nums.length - 1; i; --i) {
        if (nums[i - 1] >= nums[i]) {
            return i;
        }
    }
    return 0;
}

评论