솔루션: 제한된 최대값을 가진 하위 배열의 수

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #795(중간): 제한된 최대값을 가진 하위 배열의 수

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

We are given an array nums of positive integers, and two positive integers left and right (left <= right).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least left and at most right.

예:

Example 1:
Input:	nums = [2, 1, 4, 3] left = 2 right = 3
Output:	3
Explanation:	There are three subarrays that meet the requirements: [2], [2, 1], [3].

제약:

• left, right, and nums[i] will be an integer in the range [0, 10^9].
• The length of nums will be in the range of [1, 50000].

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

이 문제의 핵심은 겹치는 삼각수 문제를 다루고 있다는 사실을 깨닫는 것입니다. 중요한 것은 더 큰 하위 배열 내에 포함된 가능한 하위 배열의 총 수는 N번째 삼각수이며 여기서 N은 더 큰 하위 배열의 길이입니다.

따라서 nums 배열은 (nums.length)번째 삼각형 숫자 전체 하위 배열로 시작합니다. 그러나 우리는 오른쪽보다 큰 숫자를 포함하는 하위 배열을 제외하려고 합니다. 이를 수행하는 가장 쉬운 방법은 오른쪽보다 큰 숫자를 분할자로 간주하여 숫자를 여러 하위 배열로 나누는 것입니다. 이러한 결과 하위 배열 각각에 대한 삼각형 수를 함께 더하여 오른쪽보다 큰 숫자를 제외하는 하위 배열의 총 수를 더할 수 있습니다.

이를 위해 숫자를 반복하고 얼마나 많은 연속 숫자가 오른쪽(mid)보다 작은지 추적하고 mid가 증가하는 각 포인트를 추적하여 다음 삼각형 숫자의 증가를 나타내는 ans에 mid를 추가할 수 있습니다. 중간 값은 오른쪽보다 높은 숫자를 볼 때마다 재설정됩니다.

그러나 이것은 문제의 절반에 불과합니다. 왜냐하면 우리는 여전히 적어도 상위에 남아 있는 숫자가 없는 하위 배열도 제외해야 하기 때문입니다. 이를 위해 mid와 유사한 방법을 사용할 수 있습니다. 얼마나 많은 연속 숫자가 왼쪽(낮음)보다 낮은지 추적하고 증가할 때마다 ans를 감소시켜 다음 삼각형 숫자를 나타낼 수 있습니다. mid와 유사하게, low는 적어도 high로 남겨진 숫자를 볼 때마다 재설정됩니다.

반복이 끝나면 ans를 반환할 수 있습니다.

시각적 예:

시간 복잡도: O(N) 여기서 N은 숫자의 길이임

공간 복잡도: O(1)

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var numSubarrayBoundedMax = function(nums, left, right) {
    let ans = 0, low = 0, mid = 0
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i]
        if (num > right) mid = 0
        else ans += ++mid
        if (num >= left) low = 0
        else ans -= ++low
    }
    return ans
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        ans, low, mid = 0, 0, 0
        for num in nums:
            if num > right: mid = 0
            else:
                mid += 1
                ans += mid
            if num >= left: low = 0
            else:
                low += 1
                ans -= low
        return ans

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int ans = 0, low = 0, mid = 0;
        for (int num : nums) {
            if (num > right) mid = 0;
            else ans += ++mid;
            if (num >= left) low = 0;
            else ans -= ++low;
        }
        return ans;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int ans = 0, low = 0, mid = 0;
        for (auto num : nums) {
            if (num > right) mid = 0;
            else ans += ++mid;
            if (num >= left) low = 0;
            else ans -= ++low;
        }
        return ans;
    }
};