Medium

题目描述

给你一个整数数组 arr，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。

返回满足题意的最短子数组的长度。

子数组 定义为数组中任意个连续的元素。

示例 1：

输入：arr = [1,2,3,10,4,2,3,5]
输出：3
解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素为 [1,2,3,3,5] 。
另一个正确的解是删除子数组 [3,10,4] 。

示例 2：

输入：arr = [5,4,3,2,1]
输出：4
解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么是 [5,4,3,2]，要么是 [4,3,2,1]。

示例 3：

输入：arr = [1,2,3]
输出：0
解释：数组已经是非递减的了。我们不需要删除任何元素。

提示：

  • 1 <= arr.length <= 10^5
  • 0 <= arr[i] <= 10^9

解题思路

这道题的核心思想是：删除子数组后，剩余部分是左边一个非递减的前缀和右边一个非递减的后缀的拼接。

解题思路：

  1. 寻找左边界：从左开始找到最长的非递减前缀，记录边界 left
  2. 寻找右边界：从右开始找到最长的非递减后缀，记录边界 right
  3. 三种情况：
    • 保留左前缀：删除 [left+1, n-1]
    • 保留右后缀：删除 [0, right-1]
    • 保留左前缀+右后缀：使用双指针找到能连接的最佳组合

对于第三种情况，我们需要确保左前缀的最后一个元素 ≤ 右后缀的第一个元素。通过双指针遍历所有可能的组合，找到删除子数组长度的最小值。

时间复杂度： O(n)，每个元素最多被访问常数次 空间复杂度： O(1)，只使用常量额外空间

这种方法避免了复杂的分情况讨论，通过统一的双指针框架解决问题。

代码实现

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        
        // 找到左边最长的非递减序列
        int left = 0;
        while (left + 1 < n && arr[left] <= arr[left + 1]) {
            left++;
        }
        
        // 如果整个数组已经是非递减的
        if (left == n - 1) return 0;
        
        // 找到右边最长的非递减序列
        int right = n - 1;
        while (right > 0 && arr[right - 1] <= arr[right]) {
            right--;
        }
        
        // 三种情况的最小值
        int result = min(n - left - 1, right);
        
        // 尝试保留左前缀和右后缀
        int i = 0, j = right;
        while (i <= left && j < n) {
            if (arr[i] <= arr[j]) {
                result = min(result, j - i - 1);
                i++;
            } else {
                j++;
            }
        }
        
        return result;
    }
};

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        
        # 找到左边最长的非递减序列
        left = 0
        while left + 1 < n and arr[left] <= arr[left + 1]:
            left += 1
        
        # 如果整个数组已经是非递减的
        if left == n - 1:
            return 0
        
        # 找到右边最长的非递减序列
        right = n - 1
        while right > 0 and arr[right - 1] <= arr[right]:
            right -= 1
        
        # 三种情况的最小值
        result = min(n - left - 1, right)
        
        # 尝试保留左前缀和右后缀
        i, j = 0, right
        while i <= left and j < n:
            if arr[i] <= arr[j]:
                result = min(result, j - i - 1)
                i += 1
            else:
                j += 1
        
        return result

public class Solution {
    public int FindLengthOfShortestSubarray(int[] arr) {
        int n = arr.Length;
        
        // 找到左边最长的非递减序列
        int left = 0;
        while (left + 1 < n && arr[left] <= arr[left + 1]) {
            left++;
        }
        
        // 如果整个数组已经是非递减的
        if (left == n - 1) return 0;
        
        // 找到右边最长的非递减序列
        int right = n - 1;
        while (right > 0 && arr[right - 1] <= arr[right]) {
            right--;
        }
        
        // 三种情况的最小值
        int result = Math.Min(n - left - 1, right);
        
        // 尝试保留左前缀和右后缀
        int i = 0, j = right;
        while (i <= left && j < n) {
            if (arr[i] <= arr[j]) {
                result = Math.Min(result, j - i - 1);
                i++;
            } else {
                j++;
            }
        }
        
        return result;
    }
}

var findLengthOfShortestSubarray = function(arr) {
    const n = arr.length;
    
    // Find the longest non-decreasing prefix
    let left = 0;
    while (left < n - 1 && arr[left] <= arr[left + 1]) {
        left++;
    }
    
    // If the entire array is already sorted
    if (left === n - 1) return 0;
    
    // Find the longest non-decreasing suffix
    let right = n - 1;
    while (right > 0 && arr[right - 1] <= arr[right]) {
        right--;
    }
    
    // Option 1: Remove everything after the prefix
    let result = right;
    
    // Option 2: Remove everything before the suffix
    result = Math.min(result, left + 1);
    
    // Option 3: Remove elements in the middle by merging prefix and suffix
    let i = 0, j = right;
    while (i <= left && j < n) {
        if (arr[i] <= arr[j]) {
            result = Math.min(result, j - i - 1);
            i++;
        } else {
            j++;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(1)

相关题目