文章目錄

• • 題目
  • 滑動窗口思路
  • dp思路
  • 滑動窗口高效

標簽：sliding window， 滑動窗口

題目

A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulentif and only if:

• For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
• OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: [9,4,2,10,7,8,8,1,9] Output: 5 Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

Input: [4,8,12,16] Output: 2

Example 3:

Input: [100] Output: 1

Note:

1 <= A.length <= 40000

0 <= A[i] <= 10^9

滑動窗口思路

// // Created by hanshan on 19-6-14. //#include <vector> using namespace std;class Solution { public:int maxTurbulenceSize(vector<int>& A) {if(A.size() == 1){return A.size();}int i;for(i=1; i<A.size(); i++){if(A[i] != A[i-1]) break;}if (i == A.size())return 1;int ct = 2;int ans = 2;for(i=1; i<A.size()-1; i++){if(A[i-1] < A[i] && A[i] > A[i+1]){ct ++;}else if(A[i-1] > A[i] && A[i] < A[i+1]){ct ++;}else{ct = 2;}ans = max(ct, ans);}return ans;} };

dp思路

class Solution { public:int maxTurbulenceSize(vector<int>& A) {if(A.size() == 1) return 1;vector<int> dp(A.size());dp[0] = 1;if(A[1] == A[0]) dp[1] = 1;else dp[1] = 2;int ans = dp[1];for(int i=2; i<A.size(); i++){if(A[i] > A[i-1] && A[i-1] < A[i-2]) dp[i] = dp[i-1] + 1;else if(A[i] < A[i-1] && A[i-1] > A[i-2]) dp[i] = dp[i-1] +1;else if(A[i] == A[i-1]) dp[i] = 1;else dp[i] = 2;ans = max(ans, dp[i]);}return ans;} };

滑動窗口高效

int maxTurbulenceSize(vector<int>& A, int res = 0) {for (auto i = 0, cnt = 0; i + 1 < A.size(); ++i, cnt *= -1) {if (A[i] > A[i + 1]) cnt = cnt > 0 ? cnt + 1 : 1;else if (A[i] < A[i + 1]) cnt = cnt < 0 ? cnt - 1 : -1;else cnt = 0;res = max(res, abs(cnt));}return res + 1; }

總結

以上是生活随笔為你收集整理的978 Longest turbulent subarray的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。