数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中最长湍流子数组
考虑数组 A[i]、A[i+1]、...、A[j] 的子数组，当它满足以下条件时，被称为湍流：−
对于 i <= k < j 且 k 为奇数时 A[k] > A[k+1]，k 为偶数时 A[k] < A[k+1]；
否则，对于 i <= k < j，k 为偶数时 A[k] > A[k+1]，k 为奇数时 A[k] < A[k+1]。
因此，如果子数组中每对相邻元素之间的比较符号发生翻转，则该子数组为湍流。现在找到数组 A 的最大尺寸湍流子数组的长度。因此，如果输入类似于 [9,4,2,10,7,8,8,1,9]，则输出为 5。这是因为 A[1] > A[2] < A[3] > A[4] < A[5]
为了解决这个问题，我们将遵循以下步骤：−
n := 数组 A 的大小
prevBig := 1，prevSmall := 1，currBig := 1，currSmall := 1 和 ret := 1
对于 i 的范围从 1 到 n – 1
如果 A[i] > A[i – 1]，则 currBig := 1 + prevSmall
如果 A[i] < A[i – 1]，则 currSmall := 1 + prevBig
ret := ret、currBig 和 currSmall 的最大值
prevSmall := currSmall，prevBig := currBig，currSmall := 1，currBig := 1
返回 ret
让我们看看以下实现，以便更好地理解：−
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxTurbulenceSize(vector<int>& A) {
int n = A.size();
int prevBig = 1;
int prevSmall = 1;
int currBig = 1;
int currSmall = 1;
int ret = 1;
for(int i = 1; i < n; i++){
if(A[i] > A[i - 1]){
currBig = 1 + prevSmall;
}
if(A[i] < A[i - 1]){
currSmall = 1 + prevBig;
}
ret = max({ret, currBig, currSmall});
prevSmall = currSmall;
prevBig = currBig;
currSmall = 1;
currBig = 1;
}
return ret;
}
};
main(){
vector<int> v1 = {9,4,2,10,7,8,8,1,9};
Solution ob;
cout << (ob.maxTurbulenceSize(v1));
}输入
[9,4,2,10,7,8,8,1,9]
输出
5
更新于: 2020年4月30日
316 次浏览
广告