牛客4485题 如何在O(n)时间内找出数组中的"乱序段" 最短排序子数组问题详解

问题描述与理解

想象你面前有一排数字卡片，它们本应是按顺序排列的，但中间有一段被打乱了。你的任务是找出这段打乱区域的最短长度。例如：

• 原始数组：[2,6,4,8,10,9,15]

• 需要排序的最短子数组：[6,4,8,10,9]

• 结果：5

算法思路拆解

第一步：边界初步确定

我们从数组两端出发寻找边界：

1. 从左向右：找到第一个"下降点"（即前一个数比后一个数大）

2. 从右向左：找到第一个"上升点"（即后一个数比前一个数小）

第二步：确定极值范围

在初步确定的范围内：

1. 找出这段子数组的最小值(min_val)

2. 找出这段子数组的最大值(max_val)

第三步：边界扩展

检查边界是否需要扩展：

1. 向左扩展：如果左边有比min_val更大的数

2. 向右扩展：如果右边有比max_val更小的数

代码逐行解析

class ShortSubsequence {
  public:
    int findShortest(vector<int> A, int n) {
        int start = 0, end = n - 1;

        // 从左往右找第一个下降点
        while (start < n - 1 && A[start] <= A[start + 1]) start++;
        if (start == n - 1) return 0; // 已经有序

        // 从右往左找第一个上升点
        while (end > 0 && A[end] >= A[end - 1]) end--;

        // 找出中间段的最小最大值
        int min_val = *min_element(A.begin() + start, A.begin() + end + 1);
        int max_val = *max_element(A.begin() + start, A.begin() + end + 1);

        // 向左扩展
        while (start > 0 && A[start - 1] > min_val) start--;

        // 向右扩展
        while (end < n - 1 && A[end + 1] < max_val) end++;

        return end - start + 1;
    }
};

复杂度分析

• 时间复杂度：O(n)，因为每个元素最多被访问3次

• 空间复杂度：O(1)，只使用了常数个临时变量

常见误区与调试技巧

1. 边界条件：特别注意全有序数组的情况

2. 极值范围：确保min_val和max_val来自正确的区间

3. 扩展逻辑：注意扩展时数组越界的可能性