Count Subarrays With Fixed Bounds

문제 설명

• 정수 배열 nums와 두 정수 minK, maxK가 주어집니다.
• "fixed-bound subarray" 는 다음 조건을 만족하는 부분 배열입니다.
  • 부분 배열의 최솟값이 정확히 minK입니다.
  • 부분 배열의 최댓값이 정확히 maxK입니다.
• "fixed-bound subarray" 의 개수를 반환해야 합니다.

문제 풀이

Sliding Window

💡 아이디어

fixed-bound subarray의 조건을 다음과 같이 생각할 수 있습니다.

• minK보다 작거나, maxK보다 큰 값을 가지면 안됩니다.
• minK와 maxK의 값을 가지고 있어야합니다.

1. 배열을 순차적으로 순회합니다
2. 범위 밖의 값(num < minK || num > maxK) 발견시 윈도우 재설정합니다.
3. minK와 maxK 발견 시 각각의 마지막 위치를 갱신합니다.
4. 현재 윈도우 내에 minK와 maxK 모두 존재하면 다음을 실행합니다.
   • 가능한 부분 배열 개수 = Math.min(lastMinIndex, lastMaxIndex) - start + 1
   • 현재 윈도우에서 minK와 maxK를 모두 포함하면서 가능한 시작점의 개수와 같습니다.

export function countSubarrays(nums: number[], minK: number, maxK: number): number {
  const n = nums.length;
 
  let answer = 0;
  let start = 0;
  let lastMinIndex = -1;
  let lastMaxIndex = -1;
  for (let i = 0; i < n; i++) {
    const num = nums[i];
    if (num < minK || num > maxK) {
      start = i + 1;
    }
    if (num === maxK) {
      lastMaxIndex = i;
    }
    if (num === minK) {
      lastMinIndex = i;
    }
    if (start <= lastMinIndex && start <= lastMaxIndex) {
      answer += Math.min(lastMinIndex, lastMaxIndex) - start + 1;
    }
  }
  return answer;
}

복잡도

• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(1)$