LeetCode – 581. Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

  1. Then length of the input array is in range [1, 10,000].
  2. The input array may contain duplicates, so ascending order here means <=.

这道题放简单是因为他能用sort的办法解决:复制一个数组,然后将它sort,然后对比两个数组

但是如果有头尾指针的话,算法会更好,但是难度会更高,自己就掉坑里面去了,还好爬出来了。

这道题不能用传统的头尾指针,需要做头尾两次遍历,一次找到不同于之前的最大值和位置一次找到不同于之前的最小值和位置

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int start =-1;
        int end = -1;
        int max = nums[0];
        int min = nums[nums.length-1];
        for(int i=1;i<nums.length;i++){
            if(nums[i]<max){
                end = i;
            }
            max = Math.max(max,nums[i]);
        }
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]>min){
                start = i;
            }
            min = Math.min(min,nums[i]);
        }
        if (start == -1 && end == -1) {
            return 0;    
        } 
        return end-start+1;
    }
}

喜欢的话订阅一个呗~第一时间收到文章更新哟~

发表评论

电子邮件地址不会被公开。