581. Shortest Unsorted Continuous Subarray

leetcode.com/problems/shortest-unsorted-continuous-subarray/

Shortest Unsorted Continuous Subarray - LeetCode

 

문제:

문자 배열이 주어진다. 이것을 오름차순으로 만들기 위해 수정해야하는 배열의 길이를 구하시오.

즉, 1번 케이스에서 6 4 8 10 9 부분을 오름차순 정렬하면 전체가 오름차순이 된다. 이떄의 길이는 5이므로 

5를 리턴한다.

 

접근법: 

정렬, 문자열

 

풀이:

1) 0번 인덱스에서 nums.length까지 최대값을 탐색한다.

2) 배열끝에서 0번 인덱스까지 최소값을 탐색한다.

 

0~nums.length를 탐색하면서 최대값보다 작은 부분이 있다. 즉, 정렬이 안 된 부분이다.

 

예를들어 [6, 4] 부분  [10, 9] 부분이 정렬이 안된 부분이다.

 

이런 정렬이 잘못된 부분의 index를 저장하는 거다. 9의 index인 5를 저장한다.

최소값 찾는것도 똑같이 진행하면 된다.

 

마지막에 위의 두 index의 차를 구하면된다.

 

코드

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int max=-Integer.MAX_VALUE;
        int min =Integer.MAX_VALUE;
        int low = -1;
        int high = -1;
        int answer = 0;
        for(int i=0; i<nums.length; i++){
            if(max <= nums[i]){
                max = nums[i];
            }else{
                low = i;
            }
        }
        
        for(int j=nums.length-1; j>=0; j--){
            if(min >= nums[j]){
                min = nums[j];
            }else{
                high = j;
            }
        }
        
        if(low !=-1 && high != -1)
            answer = low- high + 1;
        return answer;
    }
}