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

6个月前 (06-15)牛客题解215

问题描述与理解

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

原始数组：[2,6,4,8,10,9,15]
需要排序的最短子数组：[6,4,8,10,9]
结果：5

算法思路拆解

第一步：边界初步确定

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

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

第二步：确定极值范围

在初步确定的范围内：

找出这段子数组的最小值(min_val)
找出这段子数组的最大值(max_val)

第三步：边界扩展

检查边界是否需要扩展：

向左扩展：如果左边有比min_val更大的数
向右扩展：如果右边有比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;
    }
};