题解 | #最短无序连续子数组# [P3]

对于i，如果满足i左侧所有数都小于i，并且i右侧所有数都大于i，那么i的位置不用变
两个条件中任意一个条件不满足，那么i就要挪位置 (充分必要)。
那不就是找出需要挪位置的最小和最大下标，求个差就行了

从左向右走一遍 判断是不是i左侧所有数都小于i
从右向左走一遍 判断是不是i右侧所有数都大于i
然后记录不满足条件的最小和最大下标。

时间: O(n)
空间: O(1)

import java.util.*;

public class Solution {
  public int findUnsortedSubarray (int[] nums) {
    int minInvalidId = Integer.MAX_VALUE;
    int maxInvalidId = Integer.MIN_VALUE;
    
    // i is valid if for all j<i, nums[j]<=nums[i]
    int leftMax = nums[0];
    for (int i = 1; i < nums.length; i++) {
      if (nums[i] < leftMax) {
        minInvalidId = Math.min(minInvalidId, i);
        maxInvalidId = Math.max(maxInvalidId, i);
      }
      leftMax = Math.max(leftMax, nums[i]);
    }
    
    // i is valid if for all k>i, nums[k]>=nums[i]
    int rightMin = nums[nums.length-1];
    for (int i = nums.length-2; i >=0; i--) {
      if (nums[i] > rightMin) {
        minInvalidId = Math.min(minInvalidId, i);
        maxInvalidId = Math.max(maxInvalidId, i);
      }
      rightMin = Math.min(rightMin, nums[i]);
    }
    
    return minInvalidId < maxInvalidId ?
      maxInvalidId - minInvalidId + 1 : 0;  // 0 if array is sorted
  }
}