https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/description/
One pass:
http://zxi.mytechroad.com/blog/algorithms/array/leetcode-795-number-of-subarrays-with-bounded-maximum/
When
The initial case: we don't have some
https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/117612/C++-O(n)-solution-with-explanations/117551?page=1
https://blog.csdn.net/u011026968/article/details/79475331
https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/117723/Python-standard-DP-solution-with-explanation
http://bookshadow.com/weblog/2018/03/04/leetcode-number-of-subarrays-with-bounded-maximum/
O(N^2)
https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/117585/Java-9-liner
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
Awill be in the range of[1, 50000].
http://zxi.mytechroad.com/blog/algorithms/array/leetcode-795-number-of-subarrays-with-bounded-maximum/
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int ans = 0;
int left = -1;
int right = -1;
for (int i = 0; i < A.size(); ++i) {
if (A[i] >= L) right = i;
if (A[i] > R) left = i;
ans += (right - left);
}
return ans;
}
https://blog.csdn.net/u014688145/article/details/79457423
先关注一波性质，在L和R之间的最大值val符合 val in [L, R]， 可以转为：求区间内的任意值x ， x in [L, R]。所以，把数组的每个位置当作起点，如A = [2, 1, 4, 3]:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
return count(A, R) - count(A, L - 1);
}
private:
// Count # of sub arrays whose max element is <= N
int count(const vector<int>& A, int N) {
int ans = 0;
int cur = 0;
for (int a: A) {
if (a <= N)
ans += ++cur;
else
cur = 0;
}
return ans;
}
https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/117616/C++-O(n)-less10-linesleft+1..right is the longest subarray so far that has an ending number (A[right]) in range L..R.When
A[i] > R, the update ensures this interval becomes empty again so the update to result can be handled uniformly in all situations.The initial case: we don't have some
A[right] in range L..R yet, so it's also empty. int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int result=0, left=-1, right=-1;
for (int i=0; i<A.size(); i++) {
if (A[i]>R) left=i;
if (A[i]>=L) right=i;
result+=right-left;
}
return result;
}
https://blog.csdn.net/u011026968/article/details/79475331
The idea is to keep track of 3 things while iterating: the number of valid subarrays (
res), the number of valid subarray starting points (heads), and the number of not-yet valid starting points (tails).- Values between
LandRare heads. Every contiguous value afterwards that is less than R afterwards can extend them, creating new subarrays. - Values less than
Lare tails. If they connect to a head later in the array, they become a head for valid subarrays. - Values greater than
Rare combo breakers. They stop all heads and tails from forming from subarrays.
Therefore, we keep a rolling count of valid subarrays as we iterate through
A, the main array.- If a
headis encountered, it joins the existing heads to form subarrays at each iteration. Alltailsare promoted to heads. All existing heads create a new valid subarray.- The new head creates subarray of a single element ([head])
- Each promoted head creates subarrays from its tail index to current index (e.g. [tail1, tail2, head, ...], encountering head promotes tail1 and tail2 to heads and creates [tail1, tail2, head] and [tail2, head])
- If a tail is encountered, all existing heads can create another subarray with it. The tail remains useless until it encounters a head (see above).
- If a combo breaker is met, all existing heads and tails become useless, and are reset to 0.
Counts of new subarrays (i.e. head count) are added to
res at each iteration, if valid. int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int res = 0, heads = 0, tails = 0;
for (int val : A) {
if (L <= val && val <= R) {
// val is a head. All tails promoted to heads
heads+= tails + 1;
tails = 0;
res += heads;
}
else if (val < L) {
// val is a tail, can extend existing subarrays
tails++;
res += heads;
}
else {
// combo breaker
heads = 0;
tails = 0;
}
}
return res;
}http://bookshadow.com/weblog/2018/03/04/leetcode-number-of-subarrays-with-bounded-maximum/
组合（Combination）
def numSubarrayBoundedMax(self, A, L, R):
"""
:type A: List[int]
:type L: int
:type R: int
:rtype: int
"""
ans = lastIdx = 0
for i, x in enumerate(A + [10**10]):
if x > R:
ans += self.numSubarrayMinimumMax(A[lastIdx:i], L)
lastIdx = i + 1
return ans
def numSubarrayMinimumMax(self, A, L):
"""
:type A: List[int]
:type L: int
:rtype: int
"""
ans = lastIdx = 0
for i, x in enumerate(A):
if x >= L:
ans += (i - lastIdx + 1) * (len(A) - i)
lastIdx = i + 1
return ansO(N^2)
https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/117585/Java-9-liner
public int numSubarrayBoundedMax(int[] A, int L, int R) {
int res = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] > R) continue;
int max = Integer.MIN_VALUE;
for (int j = i; j < A.length; j++) {
max = Math.max(max, A[j]);
if (max > R) break;
if (max >= L) res++;
}
}
return res;
}
