[LeetCode] 2444. Count Subarrays With Fixed Bounds

링크

문제

최소값과 최대값을 포함하는 서브어레이는 총 몇개인가?

제약사항

• 2 <= nums.length <= 10**5
• 1 <= nums[i], minK, maxK <= 10**6

첫번째 아이디어

최소 값과 최대값을 찾으면 그 위치부터 최소값이나 최대값의 범위가 넘어가는 구간까지의 개수를 구한다. 그리고 다음 최대값으로 넘어간다.

시간초과가 났다.
10 ** 5이기에 for문을 한번만 돌려서 해결해야 한다.

문제점

start, left, right, end 이렇게 4개를 사용하여 구현했다.
start는 시작 위치, left는 처음 만나는 최소값 or 최대값, right는 left의 반대 값, end는 right +1부터 시작해서 최소값부터 최대값 사이의 값이 아닌 위치이다.

아무리 해도 안풀려서 풀이를 확인하니 너무 허무하다.
난 오른쪽인 end부분을 집착해서 코드를 작성하다보니 이중 for문이 필수적으로 들어갔다. 하지만 왼쪽만 확인해도 결과는 같고 오히려 for문 1번으로 해결할 수 있는 문제였다.

코드

class Solution:

    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:

    n = len(nums)

    start = -1

    lastMin, lastMax = -1, -1

    ans = 0

    for i in range(n):
        if minK <= nums[i] <= maxK:
            # # lastMin이나 lastMax라면 lastMin과 lastMax 바꿈
            lastMin = i if nums[i] == minK else lastMin
            lastMax = i if nums[i] == maxK else lastMax
            # lastMin과 lastMax 2개가 모두 들어와야 
            ans += max(0, min(lastMin, lastMax) - start)
        # 사이 값이 아니기에 초기화
        else:
            start = i
            lastMin, lastMax = -1, -1

    return ans