C++ 中具有有界最大值的子数组数量
c++server side programmingprogramming
假设我们有一个由正整数组成的数组 A，以及两个正整数 L 和 R。我们需要找到(连续、非空)子数组的数量，使得该子数组中最大数组元素的值至少为 L，最多为 R。因此，如果 A = [2,1,4,3]，且 L = 2，R = 3，则输出将为 3，因为有三个子数组符合要求。它们是 [2]、[2,1]、[3]。
为了解决这个问题，我们将遵循以下步骤 −
ret := 0, dp := 0, prev := -1
for i in range 0 to size of A – 1
如果 A[i]
0，则 ret := ret + dp 如果 A[i] > R，则 prev := i 且 dp := 0
否则，当 A[i] >= L 且 A[i] <= R，则 dp := i – prev 且 ret := ret + dp
return ret
示例 (C++)
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int ret = 0;
int dp = 0;
int prev = -1;
for(int i = 0; i < A.size(); i++){
if(A[i] < L && i > 0){
ret += dp;
}
if(A[i] > R){
prev = i;
dp = 0;
}
else if(A[i] >= L && A[i] <= R){
dp = i - prev;
ret += dp;
}
}
return ret;
}
};
main(){
vector<int> v = {2,1,4,3};
Solution ob;
cout << (ob.numSubarrayBoundedMax(v, 2, 3));
}
输入
[2,1,4,3] 2 3
输出
3
