package arrays;

import java.util.Arrays;

/**
 * 题目:求需要排序的最短子数组
 * y: [0,2,4,1,8]
 * 只需要排序 2 4 1就可以使用数组递增有序,所以返回3
 *
 * @Author Gavin
 * @date 2022年01月17日 21:19
 */
public class array_16 {
 /**
 * 解题思路:
 * 第一种方法:先把数组排序,然后和元数组进行对比,左右下标进行对比,如果元数组
 * 下标对应的值和排序后下标对应的值相同就说明有序
 */
 //Time:O(N*log(n)) Space:O(n)
 public static int solution_1(int[] nums) {
 if (nums == null || nums.length == 0) return 0;
 int[] sorted = nums.clone();
 Arrays.sort(sorted);
 int i = 0, j = nums.length - 1;
 while (i < nums.length && nums[i] == sorted[i]) ++i;
 while (j >= 0 && nums[j] == sorted[j]) --j;
 return Math.max(j - i + 1, 0);
 }

 /**
 * 第二种方法:
 * 我们要明确排序后数组的特点,从左往右是依次递增的
 * 所以我们可以使用两个指针分别从左往右和从右往左依次移动,左边移动到
 * i+1 < i 的时候暂停移动,右边j移动到j < j-1 的时候暂停移动,这样就找到了两个边界值以及一个
 * 区间 i ~ j ,然后从这个区间找到最大值和最小值,拿最小值和0到i进行比较,因为此时0到i是有序的,
 * 同理用最大值和j到数组末尾进行对比,这样就能找到最小的区间了,只需要遍历两次数组,时间复杂度为
 * o(n)
 */
 public static int solution_2(int[] nums) {
 if (nums == null || nums.length == 0) return 0;
 int n = nums.length-1;
 int i = 0, j = n;
 while (i < n && nums[i + 1] >= nums[i]) ++i;
 while (j > 0 && nums[j - 1] <= nums[j]) --j;
 int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
 //求i~j之间的最大值和最小值
 for (int k = i; k <= j; ++k) {
 min = Math.min(min, nums[k]);
 max = Math.max(max, nums[k]);
 }
 while (i >= 0 && min < nums[i]) --i;//最后会多减一次
 while (j <= n && max > nums[j]) ++j;//最后会多加一次
 //i+1 ~ j-1 所以长度就为: j-1 - (i+1) +1
 return Math.max(j - i - 1, 0);//和0比较是因为如果是递增有序的数组那么j-i就是负数了
 }

 /**
 * 第三种方法:
 * 仍然是利用递增数组的特点,我们只需要遍历一次数组,同样我们使用两个指针进行移动
 * i从左到右移动,每移动一个就求最大值看是否和当前值相等(因为递增的特点),同理,j从末尾开始向左
 * 移动,并求最小值是否和当前值相等。
 * 最后求j-i+1的大小就行
 *
 * 由于递增的特点,往左能够找到最左边界的一个大值,同理,最右边能够找到一个小值的边界值
 */
 public int solution_3(int[] nums) {
 if (nums == null || nums.length == 0) return 0;
 int n = nums.length;
 int i = 0, j = -1, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
 for (int k = 0; k < n; k++) {
 max = Math.max(max, nums[k]);
 if (nums[k] != max) j = k;
 int p = n - 1 -k;
 min = Math.min(min, nums[p]);
 if (nums[p] != min) i = p;
 }
 return j - i + 1;
 }


}