[LeetCode] 795. Number of Subarrays with Bounded Maximum

난이도: Medium
주제: Array, Two Pointers

문제

정수 배열 nums와 두 정수 left, right가 주어진다.
연속된 비어 있지 않은 부분배열 중, 그 부분배열의 최댓값이 [left, right] 범위에 들어가는 것의 개수를 구한다.

Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3

• nums.length ≤ 10^5
• 0 ≤ nums[i] ≤ 10^9
• 0 ≤ left ≤ right ≤ 10^9

문제 이해

처음 읽으면 무슨 말인지 잘 안 들어온다. 예제를 전부 펼쳐 보면 명확해진다.

[2,1,4,3], 범위 [2, 3]일 때 가능한 부분배열 10개:

부분배열	최댓값	판정
[2]	2	✅
[2,1]	2	✅
[2,1,4]	4	❌ 초과
[2,1,4,3]	4	❌ 초과
[1]	1	❌ 미달
[1,4]	4	❌ 초과
[1,4,3]	4	❌ 초과
[4]	4	❌ 초과
[4,3]	4	❌ 초과
[3]	3	✅

즉 "최댓값이 범위 안에 드는 부분배열만 세라" 는 문제다.

접근

1. 브루트포스 (탈락)

모든 (i, j) 쌍에 대해 최댓값을 구하면 O(n²). n = 10^5에서 터진다.

2. 원소를 세 종류로 나눈다

핵심은 "i번째 원소에서 끝나는 유효 부분배열이 몇 개인가" 를 한 번의 순회로 구하는 것이다. 각 원소는 세 종류 중 하나다.

1. nums[i] > right (벽)
   이 원소를 포함하는 부분배열은 무조건 최댓값이 초과라 전부 탈락. 여기서 끊긴다.
2. left ≤ nums[i] ≤ right (유효)
   마지막 벽 다음 칸부터 i까지, 어디서 시작하든 i에서 끝나는 부분배열은 전부 유효하다.
   개수는 i - lastWall.
3. nums[i] < left (미달)
   혼자서는 미달이지만, 직전 유효 원소가 만든 부분배열 뒤에 붙여도 최댓값은 변하지 않는다.
   따라서 직전 개수를 그대로 이어받는다.

코드

function numSubarrayBoundedMax(nums: number[], left: number, right: number): number {
    let bounded = 0;      // 정답 누적
    let valid = 0;        // i에서 끝나는 유효 부분배열 개수
    let lastOverIdx = -1; // 마지막으로 right를 초과한 인덱스

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > right) {
            valid = 0;
            lastOverIdx = i;
        } else if (nums[i] >= left) {
            valid = i - lastOverIdx;
        }
        // nums[i] < left 이면 valid를 그대로 유지
        bounded += valid;
    }

    return bounded;
}

추적

[2,9,2,5,6], 범위 [2, 8]:

i	nums[i]	종류	lastOverIdx	valid	bounded
0	2	유효	-1	1	1
1	9	벽	1	0	1
2	2	유효	1	1	2
3	5	유효	1	2	4
4	6	유효	1	3	7

정답 7.

복잡도

• 시간: O(n), 한 번 순회
• 공간: O(1)

정리

• "최댓값이 범위 안"이라는 조건은 범위를 넘는 원소가 벽 역할을 한다는 뜻이다.
• 미달 원소는 부분배열을 새로 만들지 못하지만, 앞의 유효 원소가 만든 것을 깨지도 않는다. 그래서 valid를 유지만 하면 된다.
• 이 두 가지를 잡으면 한 번의 순회로 끝난다.