8月3日每日一题，=A=，今天才知道还有每日一题这个东西。
给你一个整数数组 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
进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
Related Topics
题解
最直接能想到的解法。
1，把原数组排序。
2，从左到右遍历把排序数组和原数组对比，找到需要调整的左边界。
3，从右向左遍历把排序数组和原数组对比，找到需要调整的右边界。
4，左右边界中间部分就是需要重新排序的最短区间
复杂度取决于使用的排序算法。
那么，从上面的已知的思路可以看出来，需要找到的是左边起顺序的递增的区间，和右边起倒序递减的区间。
在两边的区间里（不含中间无序部分）第i位都比左边i-n位大，都比右边第i+n位小。
所以：
1，从左向右遍历，记录找到的最大值，如果当前值比最大值小，说明当前值应该在已知最大值的左边，当前位置需要调整，记录位置rangeR
2，同理，从右向左遍历，记录找到的最小值，如果当前的值比已知最小值大，说明当前值应该在已知的最小值右边，当前位置需要调整,记录位置rangeL
3，最终需要调整的区间为rangeR到rangeL
这里可以取个巧，用双指针，一次遍历，一个指针从头向尾部遍历，另一个指针从尾部像头部遍历。这样双指针的作法减少另一次遍历循环
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
/**
* 从左向右找最大值
* 如果当前值比最大值小，说明当前值应该在已知最大值的左边，当前位置需要调整，记录位置rangeR
*
* 同理，从右向左找最小值，
* 如果当前的值比已知最小值大，说明当前值应该在已知的最小值右边，当前位置需要调整,记录位置rangeL
*
* 最终需要调整的区间为rangeR-rangeL
* @param nums
* @return
*/
public int findUnsortedSubarray(int[] nums) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int rangeL = nums.length-1;
int rangeR = 0;
for (int l = 0; l < nums.length; l++) {
int r = nums.length - l - 1;
max = Math.max(nums[l],max);
min = Math.min(nums[r],min );
if (nums[l]<max){
rangeR = l;
}
if (nums[r]>min){
rangeL = r;
}
}
return rangeR>rangeL?rangeR-rangeL+1:0;
}
}
//leetcode submit region end(Prohibit modification and deletion)
发表评论