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
以上是 C ++中有效子数组的数量 的全部内容， 来源链接： utcz.com/z/360521.html
