LeetCod : 581. Shortest Unsorted Continuous Subarray 最短非序连续子数组

Love The Way You Lie 2021-06-24 16:11 271阅读 0赞

**试题**  
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:  
Then length of the input array is in range \[1, 10,000\].  
The input array may contain duplicates, so ascending order here means <=.

**代码**  
直观感受，因为只有一个非序子数组，那么它一定在数组的中间。那么存在有序的只能在数组的两边。也就是我们需要找到非序子数组的最大值和最小值。左边有序部分需要小于最小值，右边有序部分需要大于最大值。  
简单方法，排序数组然后比较：

class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int[] snums = new int[nums.length];
            for(int i=0; i<nums.length; i++) snums[i] = nums[i];
            Arrays.sort(snums);
            
            int left = -1;
            while(left+1<nums.length && snums[left+1]==nums[left+1]) left++;
            left++;
            
            int right = nums.length;
            while(right-1>=0 && snums[right-1]==nums[right-1]) right--;
            right--;
            
            if(left>=right){
                return 0;
            }else{
                return right-left+1;
            }
        }
    }

另外就是可以利用栈，如果我们假设数组前面部分是有序，我们直接压入栈，然后加入无序部分，当我们找到一个小值时就将栈内数据弹出。

public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            Stack<Integer> stack = new Stack <Integer>();
            
            int l = nums.length, r = 0;
            for (int i = 0; i < nums.length; i++) {
                while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
                    l = Math.min(l, stack.pop());
                stack.push(i);
            }
    
            stack.clear();
            
            for (int i = nums.length - 1; i >= 0; i--) {
                while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
                    r = Math.max(r, stack.pop());
                stack.push(i);
            }
            
            return  l<r? r-l+1 : 0;
        }
    }