581. 最短无序连续子数组****【力扣】

题意理解

找出一个数组中的最短无序连续子数组，要求是对这个子树组升序排序，全数组就是顺序排序。

问题分析

要找到这样的子序列实际就是找到这个子序列的左右边界。

左边界的左边和右边界的右边都是递增的。那么左右边界的点一定是落在这两个递增序列上。

进一步分析，具体落得位置与中间部分的最小，最大值有关。以左边序列为例，比中间部分最小值小的部分可以稳定不懂，比最小值大的部分需要重排。

此算法复杂度是O（n）。

其他

0808：问题分解如何找到基本递增序列中最后一个非递增点，如何找到一个基本递减序列中最后一个非递减点。

链接

int findUnsortedSubarray(vector<int>& nums) {
        int m = nums[0], n = nums.back(), len = nums.size();    //m数组最大元素，n数组最小元素
        int l = -1, r = -2;    //l，r左右边界
        for (int i = 0; i != nums.size(); i ++)    //遍历数组
        {
            m = max(m, nums[i]);    //当前最大元素
            if (m != nums[i]) {    //当前元素是最大元素
                r = i;    //右边
            }
            n = min(n, nums[len - i - 1]);    //反向当前最小元素
            if (n != nums[len - i - 1])    //反向当前元素是最小元素
            {
                l = len - i - 1;    //左边
            }
        }
        cout << "l r " << l << '\t' << r << endl;
        return r - l + 1;    //
    }
           

int findUnsortedSubarray(vector<int>& nums) {
        int len = nums.size();
        if (len == 1) {    //长度小于等于1
            return 0;    //不存在这样的子数组
        }
        int min_value = INT_MAX;    //记录左边递增序列之后的最小值
        for (int i = 1; i <= len - 1; i ++) {
            if (nums[i] < nums[i-1]) {
                min_value = min(min_value, nums[i]);
            }
        }
        int max_value = INT_MIN;    //记录右边递减序列之后的最大值
        for (int j = len - 2; j >= 0; j --) {
            if (nums[j] > nums[j+1]) {
                max_value = max(max_value, nums[j]);
            }
        }
        int k = 0, l = len - 1;    //
        for (k = 0; k <= len - 1; k ++) {    //以最小值重新确定左边界
            if (nums[k] > min_value) break;
        }
        for (l = len - 1; l >= 0; l --) {    //以最大值重新确定右边界
            if (nums[l] < max_value) break;
        }
        return l - k < 0 ? 0 : l - k + 1;
    }