Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/795.html
795. Number of Subarrays with Bounded Maximum (Medium)
We are given an array A
of positive integers, and two positive integers L
and R
(L <= R
).
Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L
and at most R
.
Example : Input: A = [2, 1, 4, 3] L = 2 R = 3 Output: 3 Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
Note:
- L, R and
A[i]
will be an integer in the range[0, 10^9]
. - The length of
A
will be in the range of[1, 50000]
.
Companies:
Adobe
Related Topics:
Array
Solution 1.
Let’s pretend each element is either 0
if it is less than L
; 1
if it is between L
and R
; or 2
if it is greater than R
.
Since the subarray cannot contain 2
, so we look for this pattern.
2 0 0 1 0 1 0 2
That is, a subarray surrounded by 2
. We look within this subsequence.
There can be multiple 1
s in the subarray. Now the question is: count subarrays that contain at least one 1
.
In this solution, I choosed to look at the 1
s one by one.
For the first 1
:
v
2) 0 0 1 0 1 0 (2
There are 2
zeros to its left, and 3
zero/ones to its right. So the count of subarray containing this 1
is (2 + 1) * (3 + 1) = 12
.
Then for the next 1
:
x v
2) 0 0 1 0 1 0 (2
To prevent recount the subarrays containing the first 1
, we only look at the zeros to its left, and the count of which is 1
. And there are 1
zero/ones to its right. So the count of subarray containing this second 1
but not the first 1
is (1 + 1) * (1 + 1) = 2
.
So the answer should be 12 + 2 = 14
.
// OJ: https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int N = A.size(), begin = 0, maxVal = INT_MIN, cnt = 0;
while (begin < N) {
int end = begin;
while (end < N && A[end] <= R) {
maxVal = max(maxVal, A[end++]);
}
if (maxVal >= L) {
while (true) {
int i = begin;
while (i < end && A[i] < L) ++i;
if (i == end) break;
cnt += (i - begin + 1) * (end - i);
begin = i + 1;
}
}
begin = end + 1;
}
return cnt;
}
};
-
class Solution { public int numSubarrayBoundedMax(int[] A, int L, int R) { int count1 = 0, count2 = 0; int curCount1 = 0, curCount2 = 0; int length = A.length; for (int i = 0; i < length; i++) { int num = A[i]; if (num <= R) curCount1++; else { count1 += curCount1 * (curCount1 + 1) / 2; curCount1 = 0; } if (num < L) curCount2++; else { count2 += curCount2 * (curCount2 + 1) / 2; curCount2 = 0; } } if (curCount1 > 0) count1 += curCount1 * (curCount1 + 1) / 2; if (curCount2 > 0) count2 += curCount2 * (curCount2 + 1) / 2; return count1 - count2; } } ############ class Solution { public int numSubarrayBoundedMax(int[] nums, int left, int right) { return f(nums, right) - f(nums, left - 1); } private int f(int[] nums, int x) { int cnt = 0, t = 0; for (int v : nums) { t = v > x ? 0 : t + 1; cnt += t; } return cnt; } }
-
// OJ: https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/ // Time: O(N) // Space: O(1) class Solution { public: int numSubarrayBoundedMax(vector<int>& A, int left, int right) { int N = A.size(), ans = 0; for (int i = 0; i < N; ++i) { if (A[i] > right) continue; int last = -1, start = i; for (; i < N && A[i] <= right; ++i) { if (A[i] >= left && A[i] <= right) last = i; if (last != -1) ans += last - start + 1; } } return ans; } };
-
class Solution: def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int: def f(x): cnt = t = 0 for v in nums: t = 0 if v > x else t + 1 cnt += t return cnt return f(right) - f(left - 1) ############ class Solution(object): def numSubarrayBoundedMax(self, A, L, R): """ :type A: List[int] :type L: int :type R: int :rtype: int """ if not A: return 0 dp = [0] * len(A) prev = -1 for i, a in enumerate(A): if a < L and i > 0: dp[i] = dp[i - 1] elif a > R: dp[i] = 0 prev = i elif L <= a <= R: dp[i] = i - prev return sum(dp)
-
func numSubarrayBoundedMax(nums []int, left int, right int) int { f := func(x int) (cnt int) { t := 0 for _, v := range nums { t++ if v > x { t = 0 } cnt += t } return } return f(right) - f(left-1) }