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.

样例

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.

注意

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

代码实现

//题目：从原数组中找到连续的长度最大的子数组，使得对该子数组进行重新升序排序后，原数组整体升序。返回该子数组的长度

//单调栈的思路(
//1.从左向右，栈中依次存储数组中单调递增的索引值
//2.从右向左，栈中依次存储数组中单调递减的索引值
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int left = nums.length - 1;
        //升序栈，从左向右找到子数组的第一个索引值left
        for (int i = 0; i < nums.length; i++) {
            //1.空栈时：1.初始态 2.后续数组中元素的值小于前面数组中元素的值，栈中元素不断弹出
            //维持一个升序单调栈
            //2.数组中元素大于栈顶元素时，说明当前元素不是需要我们求的子数组，暂时加入栈中，具体是否满足题意，仍然需要考虑后续元素的大小
            if (stack.isEmpty() || nums[i] >= nums[stack.peek()]) {
                stack.push(i);
            //遇到小于栈顶元素的元素时，弹出栈顶值，与全局变量left比较，取较小值
            } else {
                left = Math.min(left, stack.pop());
                //此时，当前元素还需要与栈中的下一个栈顶值比较，因为有可能下一个栈顶值也是满足题目要求的子数组的一员（当该元素小于栈顶元素时）
                i--;
            }
        }
        stack.clear();
        int right = 0;
        //降序栈，从右向左找到子数组的最后一个索引值right
        for (int i = nums.length - 1; i >= 0; i--) {
            //同理
            if (stack.isEmpty() || nums[i] <= nums[stack.peek()]) {
                stack.push(i);
            } else {
                right = Math.max(right, stack.pop());
                i++;
            }
        }
        return right - left > 0 ? right - left + 1 : 0;
    }
}