Medium

题目描述

给定一个整数数组 nums。

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

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

示例 1：

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

输出：4

解释：

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

示例 2：

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

输出：3

解释：

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

示例 3：

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

输出：0

解释：

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

约束条件：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

提示：

  • 从右边找到第一个索引 i，使得 nums[i] >= nums[i + 1]。
  • 如果存在这样的索引，答案是 i + 1；否则，数组已经严格递增。

解题思路

解题思路

这道题的关键在于理解题意：我们需要找到最小的前缀长度，移除后剩余的数组严格递增。

核心观察： 如果数组已经严格递增，则不需要移除任何前缀。如果不是严格递增，那么从右往左找到第一个不满足严格递增条件的位置，移除到该位置为止的所有元素即可。

算法步骤：

  1. 从数组末尾开始向前遍历
  2. 找到第一个位置 i，使得 nums[i] >= nums[i+1]（违反严格递增）
  3. 如果找到这样的位置，说明需要移除前 i+1 个元素
  4. 如果没找到，说明数组已经严格递增，返回 0

时间复杂度分析： 最坏情况下需要遍历整个数组一次，时间复杂度为 O(n)。

空间复杂度分析： 只使用常数额外空间，空间复杂度为 O(1)。

这是一个贪心算法，因为我们总是希望保留尽可能多的元素，所以从右边开始找到第一个破坏严格递增性质的位置就是最优解。

代码实现

class Solution {
public:
    int minimumPrefixLength(vector<int>& nums) {
        int n = nums.size();
        
        // 从右往左找第一个不满足严格递增的位置
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] >= nums[i + 1]) {
                return i + 1;
            }
        }
        
        // 数组已经严格递增
        return 0;
    }
};

class Solution:
    def minimumPrefixLength(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 从右往左找第一个不满足严格递增的位置
        for i in range(n - 2, -1, -1):
            if nums[i] >= nums[i + 1]:
                return i + 1
        
        # 数组已经严格递增
        return 0

public class Solution {
    public int MinimumPrefixLength(int[] nums) {
        int n = nums.Length;
        
        // 从右往左找第一个不满足严格递增的位置
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] >= nums[i + 1]) {
                return i + 1;
            }
        }
        
        // 数组已经严格递增
        return 0;
    }
}

var minimumPrefixLength = function(nums) {
    const n = nums.length;
    
    // 从右往左找第一个不满足严格递增的位置
    for (let i = n - 2; i >= 0; i--) {
        if (nums[i] >= nums[i + 1]) {
            return i + 1;
        }
    }
    
    // 数组已经严格递增
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 最坏情况下需要遍历整个数组
空间复杂度O(1) - 只使用常数额外空间