581. Shortest Unsorted Continuous Subarray

Sort

T: O(nlogn)

mono stack

T: O(n)

S: O(n)

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new ArrayDeque<>();

        int start = n;
        int end = -1;
        
        // find left boundary
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                
                start = Math.min(start, stack.peek());
                stack.pop();
            }
            stack.push(i);
        }
        
        stack.clear();
        
        // find right boundary
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                
                end = Math.max(end, stack.peek());
                stack.pop();
            }
            stack.push(i);
        }
        return Math.max(end - start + 1, 0); // in total acs arrays [1,2,3,4] or [1], result will be negative
    }
}

/*


9
15

*/

python

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = n, -1
        
        stack = [];
        
        for i in range(n):
            while stack and nums[i] < nums[stack[-1]]:
                left = min(left, stack.pop())
            stack.append(i)
            
        for i in range(n - 1, -1, -1):
            while stack and nums[i] > nums[stack[-1]]:
                right = max(right, stack.pop())
            stack.append(i)
            
        return max(right - left + 1, 0)

new

題解可看 labu

```java
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int start = Integer.MAX_VALUE;
        int end = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                start = Math.min(start, stack.pop()); // 1
            }
            stack.push(i);
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                end = Math.max(end, stack.pop()); // 5
            }
            stack.push(i);
        }
        return start == Integer.MAX_VALUE ? 0 : end - start + 1;
    }
}
```

```java
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int first = Integer.MAX_VALUE;
        int second = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                first = Math.min(first, stack.pop());
                System.out.println("first:"+first);
            }
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                second = Math.max(second, stack.pop());
                System.out.println("second:"+second);
            }
            stack.push(i);
        }
        return first == Integer.MAX_VALUE ? 0 : second - first + 1;
    }
}

/*
0 1 2 3 4  5
2 6 4 8 10 9 15

15
9
10 -> 4 -> you can see this, not right bound , right bound is in next one position, so we should from end to do mono stack again(但相反比較直)
8
4
 -> 1  left bound!!
2


1 3 2 2 2


from right

3 1
2 2 -> pop
2 3 -> pop
2 4 -> pop -> so second = 4 (right bound)

from left -> 
  
2 
3 -> 1 pop -> so first = 1 (left bound)
1

ans: 4 - 1+ 1 = 4
*/
```