Shortest Unsorted Continuous Subarray
给一个数组, 找最小排序大小的子数组可让数组排序.
这题是双指针, 从左侧找最大值, 然后可以知道最大值右边的数字都是应该被sort的,因为如果是已经排序的数组, 最大值应该在最右侧. 同理, 我们再弄一个指针从右往左走. 然后去两个指针之差
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { public int findUnsortedSubarray(int[] nums) { int left = 0; int max = nums[0]; int n = nums.length; for(int i = 1; i < n; i++) { if(nums[i] >= max){ max = nums[i]; } else { left = i; } } int right = n - 1; int min = nums[n - 1]; for(int i = n - 1; i >= 0; i--) { if(nums[i] <= min){ min = nums[i]; } else { right = i; } } if(left == 0 && right == n - 1) return 0; return left - right + 1; } } |