[LeetCode] 1574. Shortest Subarray to be Removed to Make Array Sorted

https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/description/?envType=daily-question&envId=2024-11-15

leetcode - Shortest Subarray to be Removed to Make Array Sorted

문제 유형: 그리디, 투 포인터

문제 난이도: Medium

 

문제

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

Return the length of the shortest subarray to remove.

A subarray is a contiguous subsequence of the array.

 

정수 배열 arr이 주어집니다.

비내림차순 배열이 되도록 요소를 없앨 수 있는데, 최소개수로 없애는 수를 구하시오.

 

풀이

비내림차순 배열을 만들기 위해, 양쪽의 최선의 비내림차순 부분배열을 만들어본다.

왜냐하면 맨 왼쪽에는 작은 수들이, 맨 오른쪽에는 큰 수들이 와야 하기 떄문이다.

 

그렇게 두 부분배열을 구해서, 병합한다.

 

전체 길이에서 그 병합된 부분의 길이가 빠진게 정답이다.

 

 

코드

C++

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        int left = 0;
        int right = n-1;
        while(left < n-1 && arr[left+1] >= arr[left]) left++;
        if(left == n-1) return 0;
        while(right > 0 && arr[right-1] <= arr[right]) right--;
        int ans = min(n - left - 1, right);

        int i = 0, j = right;
        while(i <= left && j < n) {
            if(arr[i] <= arr[j]) {
                ans = min(ans, j-i-1);
                i++;
            } else {
                j++;
            }
        }

        return ans;
    }
};