[PS][LeetCode][Swift] Shortest Unsorted Continuous Subarray

581. Shortest Unsorted Continuous Subarray

Problem

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.

Input / Output

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5

Example 2:

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

Example 3:

Input: nums = [1]
Output: 0

Code

class Solution {
    var nums: [Int] = []
    let INF = 987654321
    func upperBound(_ s: Int, _ e: Int, _ target: Int) -> Int {
        var s = s, e = e
        
        while s < e {
            let mid = (s + e) / 2
            if nums[mid] <= target { s = mid + 1}
            else { e = mid }
        }
        return e
    }
    
    func lowerBound(_ s: Int, _ e: Int, _ target: Int) -> Int {
        var s = s, e = e
        
        while s < e {
            let mid = (s + e) / 2
            if nums[mid] < target { s = mid + 1}
            else { e = mid }
        }
        return e
    }
    
    func findStartNode() -> Int {
        for i in 1..<nums.count {
            if nums[i] < nums[i - 1] {
                return i - 1
            }
        }
        return -1
    }
    
    func findEndNode() -> Int {
        for i in (0..<(nums.count - 1)).reversed() {
            if nums[i] > nums[i + 1] {
                return i + 1
            }
        }
        return -1
    }
    
    func findUnsortedSubarray(_ nums: [Int]) -> Int {
        self.nums = nums
        
        let startNode = findStartNode()
        if startNode == -1 { return 0 }
        let endNode = findEndNode()
        if endNode == -1 { return nums.count }
        
        var maxVal = -INF, minVal = INF
        
        for i in startNode...endNode {
            maxVal = max(maxVal, nums[i])
            minVal = min(minVal, nums[i])
        }
        let s = upperBound(0, startNode, minVal)
        let e = lowerBound(endNode, nums.count, maxVal)
        
        return e - s
    }
}

Review

• 처음 생각난건 역시 완전 탐색이지만, 제한 조건에 배열 크기를 보면 어림도 없는 방법이란걸 알 수 있다.
• 두 번째로 생각한 것은 문제에서도 말하고 있듯 이 배열은 단조롭게 증가를 해야하는데 그 부분의 길이를 찾아주는데 있어서는 Stack 을 통해서 찾아 볼 수 있지 않을까? 라는 생각 까지 했다.
• 그리고 마지막으로 생각 난 것이 내가 풀이 방식에 써놓은 것 이다.
• 내가 생각한 Stack 을 사용하는 것은 최소 2번 이상 순회를 해야하지만, 위의 코드 방식대로 쓰면 전체는 딱 한번 탐색하고 나머지는 2 * log(N) 정도의 추가 탐색이 있을 뿐이라 저 방식을 사용했다.
• 솔루션을 보니 Without Using Extra Space? 접근 방법이 있는데 읽어보고 알아두면 좋겠다 싶다.