免费网站免费无遮挡,做视频必须知道的一些网站,网页设计主题描述,收图片的网站给你一个整数数组 nums #xff0c;你需要找出一个 连续子数组 #xff0c;如果对这个子数组进行升序排序#xff0c;那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组#xff0c;并输出它的长度。 示例 1#xff1a;
输入#xff1a;nums [2,6,4,8,10…给你一个整数数组 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 ab {return a} return b
}
func max(a,b int)int{if ab {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为0Rmin[n-1] nums[n-1]for i:n-2; i0; i-- {Rmin[i] min(nums[i], Rmin[i1])}Lmax[0] nums[0]for i:1;in;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;i0;i-- {if Lmax[i] ! nums[i] {ansr i;break;}}return ansr - ansl 1;}// [1,2,5,7,6]
