資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告