给你一个整数数组 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题报告:
时间复杂度O(nlogn)的就不说了。来看看O(n)的。
首先不难证明,如果要找的区间的左右端点也必须参与排序(即不能排序后位置不变),则这个区间是唯一的。所以就不存在最短区间这一说了,直接就找,必须参与排序的这个区间就好了。
对于我们要找到的最短区间的左端点:
从左到右扫描每一个i,如果nums[i]是后缀最小值,则他一定不是左端点,因为他不需要参与排序。因此我们只需要找到左起第一个不是后缀最小值的nums[i],那么i就是左端点。
右端点同理。
因此具体到实现方式,可以从右向左维护一个后缀最小值数组,从左到右维护一个前缀最大之数组,然后随便搞一下维护结果就好了。
AC代码:
func min(a,b int) int{
if a<b {
return a
}
return b
}
func max(a,b int)int{
if a>b {
return a
}
return b
}
func findUnsortedSubarray(nums []int) int {
n := len(nums)
Rmin := make([]int, n)
Lmax := make([]int, n)
ansl, ansr := 0,-1 //为了保证初始len为0
Rmin[n-1] = nums[n-1]
for i:=n-2; i>=0; i-- {
Rmin[i] = min(nums[i], Rmin[i+1])
}
Lmax[0] = nums[0]
for i:=1;i<n;i++ {
Lmax[i] = max(nums[i], Lmax[i-1])
}
for i,v := range(Rmin) {
if v != nums[i] {
ansl = i;
break;
}
}
for i:=n-1;i>=0;i-- {
if Lmax[i] != nums[i] {
ansr = i;break;
}
}
return ansr - ansl + 1;
}
// [1,2,5,7,6]