[leetcode]: 581. Shortest Unsorted Continuous Subarray

骑猪看日落 2022-06-14 10:07 143阅读 0赞

# 1.题目 #

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.  
给一个数组，找出其中最短的子数组，使得，将这个子数组排序后整个数组变得有序。  
Example 1:  
Input: \[2, 6, 4, 8, 10, 9, 15\]  
Output: 5  
最短无序子数组\[6, 4, 8, 10, 9\]

# 2.分析 #

目标可转换为：找到左边第一个比数组最小值大的元素和右边第一个比数组最大值小的元素。这两个元素及其中间元素构成了最短无序子数组。  
有两种实现方式。  
**方法1：**比较直观，好理解。  
将数组看做三段array=ABC，A有序，B无序，C有序  
1）找出A，B，C的分界点  
2）求B中元素的MIN，MAX  
3）求A中第一个比MIN大的元素位置x，求C中最后一个比MAX小的元素位置y。子数组长度=y-x+1

**方法2：**中心思想也是找到左边第一个比MIN大的数和右边第一个比MAX小的数  
直接看代码比较好理解

# 3.代码 #

方法1

class Solution {
    public:
        int findUnsortedSubarray(vector<int>& nums) {
            if (nums.size() < 2)
                return 0;
            int left = 0;
            int right = nums.size() - 1;
            while (left < nums.size()-1 && nums[left] <= nums[left+1])
                ++left;
            while (right > left&&nums[right-1] <= nums[right])
                --right;
            if (left == right)//整个数组有序
                return 0;
            int mid_min = INT_MAX;
            int mid_max = INT_MIN;
            for (int i = left; i <= right; i++) {
       //找中间段的最大最小值
                mid_min = mid_min > nums[i] ? nums[i] : mid_min;
                mid_max = mid_max < nums[i] ? nums[i] : mid_max;
            }
            int new_left = 0;
            while (nums[new_left] <= mid_min)//左边第一个比MIN大的元素位置
                ++new_left;
            int new_right = nums.size() - 1;
            while (nums[new_right] >= mid_max)//右边第一个比MAX小的位置
                --new_right;
            return new_right - new_left+1;
        }
    };

方法2

class Solution {
    public:
        int findUnsortedSubarray(vector<int>& nums) {
            int n = nums.size();
            int min_x = nums[n - 1];
            int max_x = nums[0];
            int beg = -1;
            int end = -2;
            for (int i = 1; i < n; i++) {
                max_x = max_x < nums[i] ? nums[i] : max_x;//从左往右，找当前最大值
                min_x = min_x > nums[n - 1 - i] ? nums[n - 1 - i] : min_x;//从右往左找当前最小值
                if (nums[i] < max_x)//小于当前最大值，说明从左到右不满足递增结构
                    end = i;
                if (nums[n - 1 - i] > min_x)//大于当前最小值，说明从右往左不满足递减结构
                    beg = n - 1 - i;
            }
            return end - beg + 1;
        }
    };