需要排序的最短子数组长度(581. Shortest Unsorted Continous Subarray)

题目描述：给定一个无序数组，求出需要排序的最短子数组的长度。例如：arr={1,5,3,4,2,6,7}返回4，因为只有[5,3,4,2]需要排序。

解题思路非原创，资料收集于如下网站，由本人整理总结：
IDeserve
leet code article

解题思路：

在网上看到过一种解题思路，从左向右遍历数组，如果某一项数组是array[i]>array[i+1]，说明遇到了第一个没有排好序的数字，记录下标为startIndex = i; 同理从右向左遍历数组，如果发现某array[j]>array[j+1]，记录下标endIndex = j; 则最短需排序的子列长度是 endIndex-startIndex+1;
但是这种想法是错误的，比如考虑数组[1,4,7,3,10,48,17,26,30,45,50,62]，按照上述的解法，我们得到startIndex在7的位置，endIndex在17的位置，那需要排序的子数组是[3,7,10,17,48]。其实这个是错误的，因为在子数组中的3和48没有在数组排好序后真正的位置上。

错误分析：

3应该在最终在1和4的中间，48应该在45和50的中间。也就是说正确算法的关键是应该是，找到最小未排序数在排序后数组的位置，和最大未排序数在排序后数组的位置。

解题思路1：用排序数组

正确算法的核心思想就是，找到最小未排序数在排序后数组的位置，和最大未排序数在排序后数组的位置。那么我们可以申请一个额外的数组和原数组一样，把它(arr_sorted)排好序，比较两个数组有哪些位置不一样，找到最左和最右的边界。

• 时间复杂度：O(N*logN); 排序
• 空间复杂度：O(N)；申请额外数组

# include <iostream>
# include <algorithm>
# include <vector>
using namespace std;

class ShortSubsequence {
public:
    int findShortest(vector<int> A, int n) {
        // copy vector A to new vector B
        vector<int> B (A);
        sort(B.begin(), B.end());
        // check the mismatch Index in both vectors
        int left = A.size();
        int right = 0;
        for (int i=0; i<A.size(); i++){
            if ( A[i] != B[i]){
                left = min(left, i);
                right = max(right, i);
            }
        }
        return right-left>=0 ? right-left+1 : 0;
    }
};

解题思路2: 利用数据结构栈

众所周知，排好序的升序数组，从左到右数组是一次递增的，也就是说，斜率一直都是非负的(arr[i+1]-arr[i] >= 0)；同理从右到左，斜率是非正的。
这样就可以利用一个栈结构，让栈顶的数与遍历数组的数(arr[i])比较，如果发现斜率不一样，就判定当前i与栈顶的Index比小，谁就是minIndex，然后把栈里面的数依次弹出与minIndex决斗，一直到找到它在原数组中排序后真正的位置，然后遍历下一个；
同理从右往左遍历，找到maxIndex；
正如下图所示，b应该在0和1之间，a应该在6和7之间。

• 时间复杂度：O(n); 数组遍历检查
• 空间复杂度：O(1)；
  

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack < Integer > stack = new Stack < Integer > ();
        int l = nums.length, r = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
                l = Math.min(l, stack.pop());
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
                r = Math.max(r, stack.pop());
            stack.push(i);
        }
        return r - l > 0 ? r - l + 1 : 0;
    }
}

解题思路3:简单的排序

承袭上面的思路，用简单的遍历比较找到，未排序数组中的MinIndex，和MaxIndex，再遍历一遍找到MinIndex在全数组的位置，同理MaxIndex；

• 时间复杂度：O(N); 4次for遍历
• 空间复杂度：O(1)；

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        boolean flag = false;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1])
                flag = true;
            if (flag)
                min = Math.min(min, nums[i]);
        }
        flag = false;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] > nums[i + 1])
                flag = true;
            if (flag)
                max = Math.max(max, nums[i]);
        }
        int l, r;
        for (l = 0; l < nums.length; l++) {
            if (min < nums[l])
                break;
        }
        for (r = nums.length - 1; r >= 0; r--) {
            if (max > nums[r])
                break;
        }
        return r - l < 0 ? 0 : r - l + 1;
    }
}