Shortest Unsorted Continuous Subarray

오늘도 Array 문제를 풀어보았다. 분명히 쉬워 보이긴 하는데 문제는.. O(n) 으로 풀어봐에서 많이 걸렸다.

무식하게 푸는 방법으로 O(n^2) 방식으로 풀었다면은 가장 Sorting 이 필요한 구간을 알 수 있었겠지만 O(n) 은 다른 방식으로 접근 해야했다.

가장 먼저, 왼쪽과 오른쪽을 기준으로 가장 작고.. 가장 큰 수를 찾아냈다.

이후에는 왼쪽부터 시작해서 가장 작은 수보다 큰 숫자 발견시 시작점으로 생각하고

오른쪽에서 시작해서 가장 큰 수보다 한번이라도 작은 숫자가 나타나면 끝나는 구간으로

이 둘의 차이를 구하면 됐었다. 솔직히 아이디어는 좀 어려운 문제인거같다.

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int min_ = INT_MAX; 
        int max_ = INT_MIN; 
        bool flag = false; 
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] < nums[i-1]){
                flag = true; 
            }
            if(flag){
                min_ = min(min_, nums[i]); 
            }
        }
        flag = false; 
        for(int i = nums.size()-2; i >= 0; i--){
            if(nums[i] > nums[i + 1]){
                flag = true;
            }
            if(flag){
                max_ = max(max_,nums[i]); 
            }
        }
        cout << min_ << ' ' << max_; 
        int l, r;  
        for(l = 0; l < nums.size(); l++){
            if(min_ < nums[l]){
                break; 
            }
        }

        for(r = nums.size()- 1; r >= 0; r--){
            if(max_ > nums[r]){
                break; 
            }
        }

        return r - 1 < 0 ? 0 : r - l + 1; 

        return max_; 
    }
};