C ++中有效子数组的数量

假设我们有一个整数数组A，我们必须找到满足以下条件的非空连续子数组的数量：子数组的最左边元素不大于子数组中的其他元素。

因此，如果输入像[1,4,2,5,3]，那么输出将为11，因为有11有效子数组，它们像[1]，[4]，[2]，[5 ]，[3]，[1,4]，[2,5]，[1,4,2]，[2,5,3]，[1,4,2,5]，[1,4,2 ，5,3]。

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

• ret：= 0

• n：= nums的大小

• 定义一个堆栈st

• 对于初始化i：= 0，当i <nums大小时，更新（将i增加1），执行-

• 从st删除元素

• x：= nums [i]

• while（不是st为空并且x <st的顶部元素），执行-

• 将x插入st

• ret：= st大小+ ret

• 返回ret

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int validSubarrays(vector<int>& nums) {
      int ret = 0;
      int n = nums.size();
      stack <int> st;
      for(int i = 0; i < nums.size(); i++){
         int x = nums[i];
         while(!st.empty() && x < st.top()) st.pop();
         st.push(x);
         ret += st.size();
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,4,2,5,3};
   cout << (ob.validSubarrays(v));
}

输入值

{1,4,2,5,3}

输出结果

11