数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律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），执行 -
x := nums[i]
当 (st 不为空且 x < st 的栈顶元素) 时，执行 -
从 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
更新于: 2020-07-11
388 次浏览
广告