# 581 Shortest Unsorted Continuous Subarray

## 581. [Shortest Unsorted Continuous Subarray](https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/)

## 1. Question

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 **<=**.

## 2. Implementation

**(1) Monotone Stack**

```java
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        int n = nums.length;
        int left = n - 1;

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                left = Math.min(left, stack.pop());
            }
            stack.push(i);
        }

        stack.clear();

        int right = 0;
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                right = Math.max(right, stack.pop());
            }
            stack.push(i);
        }

        return right - left >= 1 ? right - left + 1 : 0;
    }
}
```

## 3. Time & Space Complexity

**Monotone Stack:** 时间复杂度O(n), 空间复杂度O(n)
