LEETCODE 581: Shortest Unsorted Continuous Subarray

に質問
Given an integer array nums, 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.
Return the shortest such subarray and output its length.
Example 1:

Input: nums = [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.

Example 2:

Input: nums = [1,2,3,4]
Output: 0

Example 3:

Input: nums = [1]
Output: 0

Constraints:

1 <= nums.length <= 104
-105 <= nums[i] <= 105

Follow up: Can you solve it in O(n) time complexity?
方法
如果用O(nlogn)的时间计算量出现的话,这并不是很难的问题.
但是在O(n)的时间计算量的阿尔戈里斯姆中具現的是另一个故事.
在绘画中描绘了致力的配列数字并列的直观方式附近.
1.虽然巡回了一次配列后,
在提前的数字比较低的数字出现的瞬间(落后的时候)进行分列的min和max.
(在此时得到的min和max是整体的min和max.)
2.在搜查美分和max的巡回结束后,在配列中,搜查比最初获得的美分之高的数字和最后获得的max更低的数字index
3.引用得られたindex的话,成为整个对象的范围内.
具現(Java)

import java.util.*;

class Solution {
    
    public int findUnsortedSubarray(int[] nums) {
        
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        int left = 0, right = 0;
        
        for (int i = 0, pre = nums[0]; i < nums.length; pre = nums[i++]) {
            
            int num = nums[i];
            
            if (pre > nums[i]) {
                
                if (max <= pre) {
                    
                    max = pre;
                    right = i+1;
                }
                if (min > num)
                    min = num;
            }
        }
        
        while (left < right && nums[left] <= min) left++;
        while (right < nums.length && nums[right] < max) right++;
        
        return right-left;
    }
}