题目大意:问一个数组中有多少个子数组的最大元素值在[L, R]的范围里。
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
.
1 2 3 4 5 6 7 |
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]. |
Solution 1:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 42 ms class Solution { public: 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; } }; |
Solution 2: One pass
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 38 ms class Solution { public: 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; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment