AlgoPressAppearance
题目描述
https://leetcode.cn/problems/shortest-unsorted-continuous-subarray
给你一个整数数组 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 <= 10^4 -10^5 <= nums[i] <= 10^5
进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
思路
开始考虑复杂了，用动态规划计算两个位置(i,j)需要的范围，当 nums[j] < nums[i] 的时候就需要翻转这部分，区间为 j-i+1. 后来分析题意，题目要翻转一次，所以我们只要找出需要翻转的最左边和最右边即可。 当 nums[j] < nums[i] 分别记录 i, j 并且取最小值。
参考代码
csharp
public class Solution {
public int FindUnsortedSubarray(int[] nums) {
//如果 nums[j] < nums[i] 那么必须全部排序
int n = nums.Length;
//如果两个数相反，则表示需要排序
//找出需要排序的最小位和最大位，然后排序
int minIndex = int.MaxValue;
int maxIndex = int.MinValue;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
if(nums[j] < nums[i]){
minIndex = Math.Min(i,minIndex);
maxIndex = Math.Max(j,maxIndex);
}
}
}
if(minIndex == int.MaxValue){
return 0;
}
else{
return maxIndex - minIndex + 1;
}
}
}
思路2：进阶 O(n)
减少遍历次数 我们判断一个数字是否要去排序，就看他的右边是否有比自己小的数。 或者他的左边有没有比他大的数。 这样左右扫描两次我们可以判断左右的边界。
参考代码
csharp
public class Solution{
public int FindUnsortedSubarray(int[] nums){
int n = nums.Length;
int[] right = new int[n]; //从右往左记录最小的数
int[] left = new int[n]; //从左往右记录最大的数
int minValue = nums[n-1];
for(int i=n-1; i>=0; i--){
minValue = Math.Min(minValue,nums[i]);
right[i] = minValue;
}
int maxValue = nums[0];
for(int i=0; i<n; i++){
maxValue = Math.Max(maxValue,nums[i]);
left[i] = maxValue;
}
int leftIndex = -1;
int rightIndex = n;
for(int i=0; i<n; i++){
if(nums[i] > right[i]){
leftIndex = i;
break;
}
}
for(int i=n-1;i>=0;i--){
if(nums[i] < left[i]){
rightIndex = i;
break;
}
}
if(leftIndex == -1){
return 0;
}
else{
return rightIndex - leftIndex + 1;
}
}
}
参考代码：优化循环
一次循环， 从左往右， 计算 maxValue ，当发现 maxValue > nums[j] 说明 j 要被排序，更新 right 指针。 当发现 maxValue < nums[j] 的时候，就更新新的 maxValue 值。 这样后续遇到比这个新的 maxValue 小的值，同样更新 right 指针 同理反向计算 minValue 用 nums[n-i-1]
csharp
public class Solution{
public int FindUnsortedSubarray(int[] nums){
int n = nums.Length;
int minValue = int.MaxValue;
int maxValue = int.MinValue;
int left = -1, right = -1;
for(int i = 0; i < n; i++){
if(maxValue > nums[i]){
right = i;
}
else{
maxValue = nums[i];
}
if(minValue < nums[n-i-1]){
left = n - i -1;
}
else{
minValue = nums[n - i -1 ];
}
}
return right == -1 ? 0 : right - left + 1;
}
}
复习： 20220712 动态规划：有错误需要重新考虑
测试用例：[1,3,2,4,5] 错误 动态规划在取 min 和 max 计算的时候，有错误， nums[i] 不能直接设置为 min 我们需要的其实是 nums[i] 比后续的任何数值都小 如果使用 <= 可以判断是最小，但是如果是有重复数字，比如 [1,2,3,3,3] 则会出现错误 如果用单独的函数计算 min 和 max， 则会超时
csharp
public class Solution {
public int FindUnsortedSubarray(int[] nums) {
//动态规划
//dp[i,j]表示从i到j，最少多少数组进行升序，整个表就会变为升序
int n = nums.Length;
int max,min;
int[,] dp = new int[n,n];
for(int i=n-1; i>=0; i--){ //从后面往前计算，因为需要用到 i+1
max = nums[i]; //注意max取值范围是 i .. j-1
min = int.MaxValue; //min取值范围是 i+1..j 所以下面更新的地方不相同
for(int j=i+1; j<n; j++){
min = Math.Min(min,nums[j]);
if(j-i==1){
dp[i,j] = nums[j] < nums[i] ? 2 : 0;
}
else{
if(nums[j] >= max && nums[i] <= min){
dp[i,j] = dp[i+1,j-1];
}
else if(nums[j] >= max){
dp[i,j] = dp[i,j-1];
}
else if(nums[i] <= min){
dp[i,j] = dp[i+1,j];
}
else{
//此时所有数据都要重排
dp[i,j] = j-i+1;
}
}
max = Math.Max(max,nums[j]);
//Console.WriteLine("dp[{0},{1}]={2}",i,j,dp[i,j]);
}
}
return dp[0,n-1];
}
}
复习：20220713 直接左右计算 min max 值
基本思路： 首先判断左边界，对于i，他是否需要重新排序，取决于他是否大于他后面的数中的最小值，是的话就需要重排，这样左边界就确定了。 同样对于i，他是否要重排，取决于他是否大于他左边的最大值，如果小于，他也需要重排，这样有边界也确定了。
方法是：从后往前生成最小值数组， 从后往前生成最大值数组，然后依次比较。
csharp
public class Solution {
public int FindUnsortedSubarray(int[] nums) {
int n = nums.Length;
int[] minArr = new int[n];
int[] maxArr = new int[n];
int min = int.MaxValue;
int max = int.MinValue;
//max从前往后计算
//min从后往前计算
for(int i=0; i<n; i++){
max = Math.Max(max,nums[i]);
maxArr[i] = max;
min = Math.Min(min,nums[n-i-1]);
minArr[n-i-1] = min;
}
int start = -1;
int end = n;
for(int i=0; i<n; i++){
if(nums[i] > minArr[i]){
start = i;
break;
}
}
for(int i=n-1;i>=0; i--){
if(nums[i] < maxArr[i]){
end = i;
break;
}
}
if(start == -1){
return 0;
}
else{
return end - start + 1;
}
}
}
此方法可以优化依次循环，如下
csharp
public class Solution{
public int FindUnsortedSubarray(int[] nums){
int n = nums.Length;
int minValue = int.MaxValue;
int maxValue = int.MinValue;
int left = -1, right = -1;
for(int i = 0; i < n; i++){
//max从前往后计算
if(maxValue > nums[i]){ //如果前面更新的 maxValue 大于当前值了，说明当前的值需要被参与重排
right = i;
}
else{
maxValue = nums[i]; //如果小于当前值了，则更新最大值
}
//min从后往前计算
if(minValue < nums[n-i-1]){ //对min同样处理
left = n - i -1;
}
else{
minValue = nums[n - i -1 ];
}
}
return right == -1 ? 0 : right - left + 1;
}
}