[LeetCode] 2444. Count Subarrays With Fixed Bounds

https://leetcode.com/problems/count-subarrays-with-fixed-bounds/description/

LeetCode - Count Subarrays With Fixed Bounds

문제 유형 : 슬라이딩 윈도우

문제 난이도 : Hard

 

문제

You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

• The minimum value in the subarray is equal to minK.
• The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous part of an array.

 

정수배열 nums와 두 정수 minK와 maxK가 주어집니다.

최소값이 minK이고 최대값이 maxK인 부분배열들의 개수를 구하시오.

 

풀이

슬라이딩 윈도우가 minK보다 작거나 maxK보다 큰 값을 만나면, 그 다음부터 새로 만들어야한다.

이를 이용한 트리키한 방법이 있다.

https://leetcode.com/problems/count-subarrays-with-fixed-bounds/solutions/4949181/98-43-easy-solution-with-explanation/

의 도움을 받았다. 이전까지 비슷한 접근을 거의 했는데, 아쉽다.

 

 

우선, 유효하지 않은 값을 얻고 나서는, 그 이후로 새로 최소 값과 최대 값을 찾아야 한다. 

최소 값을 찾으면, 최소 값 인덱스를 업데이트한다.

최대 값을 찾으면, 최대 값 인덱스를 업데이트한다.

 

그 뒤, 현재까지 탐색했을 때, 만들 수 있는 부분배열의 개수를 추가하는데, 만약 유효하지 않은 값을 얻고 새로 최소값과 최대값을 찾지 못하면, 부분배열을 만들 수 없다.

새로 최소값과 최대값을 얻었다면, 둘 중 더 유효하지 않은 값의 인덱스보다 차이나는 인덱스와 유효하지 않은 값의 인덱스와의 차를 구해서 개수를 누적하면 된다.

 

코드

C++

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long ans = 0;
        int invalid_idx = -1, min_idx = -1, max_idx = -1;

        for (int i = 0; i < nums.size(); ++i) {
            if (!(minK <= nums[i] && nums[i] <= maxK)) {
                invalid_idx = i;
            }

            if (nums[i] == minK) {
                min_idx = i;
            }

            if (nums[i] == maxK) {
                max_idx = i;
            }

            ans += max(0, min(min_idx, max_idx) - invalid_idx);
        }

        return ans;
    }
};