581. 最短无序连续子数组

题目描述：

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0
示例 3：

输入：nums = [1]
输出：0
 

提示：

1 <= nums.length <= 104
-105 <= nums[i] <= 105
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
著作权归领扣网络所有。

商业转载请联系官方授权，非商业转载请注明出处。

分析：

        不是O(n)的解法就不谈了，面试没什么意义

        看题解前是不会的，看了题解后也有些迷糊，捋一捋算是明白了。

数组可以划分为三部分，左数组，中间数组，右数组，左数组和右数组是递增的，中间数组的乱序的。

但是有一点，中间数组中的任何一个元素，都大于左数组，且都小于右数组。

        我们设中间数组的左边界为left，右边界为right

        因此，从右往左遍历，维护一个最小值min，如果nums[i]<=min，则更新min，否则的话，说明nums[i]>min，那么，这个元素就有可能是中间数组的左边界left，因为中间数组的左边界，一定不是其最小值，否则左边界可以合并到左数组中。

        从左往右遍历，维护一个最大值max，如果nums[i]>=max，则更新max，否则的话，说明nums[i]

详细分析请看题解：

https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/zui-duan-wu-xu-lian-xu-zi-shu-zu-by-leet-yhlf/

代码如下：

class Solution {
public:
    int findUnsortedSubarray(vector& nums) {
        int left=-1,right=-1;
        int n=nums.size();
        int min=2147483647;
        int max=-2147483648;
        for(int i=n-1;i>=0;i--)
        {
            // 当前元素小于等于最小值，则更新最小值
            if(min>=nums[i])
            min=nums[i];
            // 否则的话，说明这个元素可能会是中间数组的左边界
            // 因为中间数组的左边界，一定不是其最小值，否则左边界可以合并到左数组中
            else 
            left=i;
            
        }
        for(int i=0;i