[Java] Daily LeetCode Challenge 2444. Count Subarrays With Fixed Bounds

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

Count Subarrays With Fixed Bounds - LeetCode

 

Hard 문제, min과 max를 모두 찾은 안정적인 상태일때마다 개수를 count 해주면 된다.

 

 

예를 들어

이런 식으로 배열이 있을 경우, 찾은 min과 max 중에서 인덱스 값이 더 작은 경우 + 앞에 있는 것들을 포함한 개수를 더해주면 된다.

동일 min ~ max 범위 내에서 앞 부분만 신경쓰고 뒷 부분은 신경써주지 않는 이유는,

어차피 i값을 옮기면서 계속 총 개수를 추가해주기 때문에 저절로 추가되는 셈이다.

 

 

주의 할 점은, min값이 무조건 앞에 있지 않다는 점! 이 점만 잘 알고 있으면 될듯하다.

그리고 이중 for문을 돌리는 건 안 봐도 타임아웃행이다. 

 

 

[코드]

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long ans = 0;

        int start = 0, minIdx = 0, maxIdx = 0;
        boolean minFound = false, maxFound = false;

        for(int i=0; i<nums.length; i++){
            int now = nums[i];

            if(now > maxK || now < minK){
                minFound = false; maxFound = false;
                start = i+1;
                continue;
            }

            if(now == maxK){
                maxFound = true;
                maxIdx = i;
            }

            if(now == minK){
                minFound = true;
                minIdx = i;
            }

            if(maxFound && minFound){
                ans += Math.min(maxIdx, minIdx) - start + 1;
            }
        }

        return ans;
    }
}