C ++中有界最大值的子数组数

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个由正整数组成的数组A，并且还给出了两个正整数L和R。我们必须找到（连续的，非空的）子数组的数量，以使该子数组中最大数组元素的值至少为L，至多为R。因此，如果A = [2,1,4,3]且L = 2和R = 3，则输出将为3，因为存在三个满足要求的子数组。因此，这些是[2]，[2,1]，[3]。

为了解决这个问题，我们将遵循以下步骤-

  • ret：= 0，dp：= 0，上一页：= -1

  • 对于范围从0到A – 1的i

    • 如果A [i] <L且i> 0，则ret：= ret + dp

    • 如果A [i]> R，则prev：= i和dp：= 0

    • 否则，当A [i]> = L且A [i] <= R时，则dp：= i – prev和ret：= ret + dp

  • 返回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

以上是 C ++中有界最大值的子数组数 的全部内容， 来源链接： utcz.com/z/331161.html

回到顶部