class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
}
};
978. 最长湍流子数组
给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
更正式地来说，当 arr 的子数组 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]。
示例 1：
输入：arr = [9,4,2,10,7,8,8,1,9] 输出：5 解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2：
输入：arr = [4,8,12,16] 输出：2
示例 3：
输入：arr = [100] 输出：1
提示：
1 <= arr.length <= 4 * 1040 <= arr[i] <= 109相似题目
原站题解
python3 解法, 执行用时: 112 ms, 内存消耗: 19.3 MB, 提交时间: 2023-09-23 00:33:45
class Solution:
'''
定义 up[i] 表示以位置 i 结尾的，并且 arr[i - 1] < arr[i] 的最长湍流子数组长度。
定义 down[i] 表示以位置 i 结尾的，并且 arr[i - 1] > arr[i] 的最长湍流子数组长度。
up[i] 和 down[i] 初始化都是 1，因为每个数字本身都是一个最小的湍流子数组。
'''
def maxTurbulenceSize1(self, arr: List[int]) -> int:
N = len(arr)
up = [1] * N
down = [1] * N
res = 1
for i in range(1, N):
if arr[i - 1] < arr[i]:
up[i] = down[i - 1] + 1
down[i] = 1
elif arr[i - 1] > arr[i]:
up[i] = 1
down[i] = up[i - 1] + 1
else:
up[i] = 1
down[i] = 1
res = max(res, max(up[i], down[i]))
return res
def maxTurbulenceSize2(self, arr: List[int]) -> int:
N = len(arr)
up = [1] * N
down = [1] * N
res = 1
for i in range(1, N):
if arr[i - 1] < arr[i]:
up[i] = down[i - 1] + 1
elif arr[i - 1] > arr[i]:
down[i] = up[i - 1] + 1
res = max(res, max(up[i], down[i]))
return res
def maxTurbulenceSize(self, A: List[int]) -> int:
if len(A) == 1 or min(A) == max(A): return 1
dp = [1] * len(A)
for i in range(1,len(A)-1):
if A[i-1] > A[i] < A[i+1] or A[i-1] < A[i] > A[i+1]:
dp[i] = dp[i-1] + 1
return max(dp) + 1
javascript 解法, 执行用时: 60 ms, 内存消耗: 46.4 MB, 提交时间: 2023-09-23 00:30:56
/**
* @param {number[]} arr
* @return {number}
*/
var maxTurbulenceSize = function(arr) {
const n = arr.length;
let ret = 1;
let left = 0, right = 0;
while (right < n - 1) {
if (left == right) {
if (arr[left] == arr[left + 1]) {
left++;
}
right++;
} else {
if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
right++;
} else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
right++;
} else {
left = right;
}
}
ret = Math.max(ret, right - left + 1);
}
return ret;
};
var maxTurbulenceSize2 = function(arr) {
const n = arr.length;
const dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
dp[0][0] = dp[0][1] = 1;
for (let i = 1; i < n; i++) {
dp[i][0] = dp[i][1] = 1;
if (arr[i - 1] > arr[i]) {
dp[i][0] = dp[i - 1][1] + 1;
} else if (arr[i - 1] < arr[i]) {
dp[i][1] = dp[i - 1][0] + 1;
}
}
let ret = 1;
for (let i = 0; i < n; i++) {
ret = Math.max(ret, dp[i][0]);
ret = Math.max(ret, dp[i][1]);
}
return ret;
};
var maxTurbulenceSize3 = function(arr) {
let ret = 1;
const n = arr.length;
let dp0 = 1, dp1 = 1;
for (let i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
dp0 = dp1 + 1;
dp1 = 1;
} else if (arr[i - 1] < arr[i]) {
dp1 = dp0 + 1;
dp0 = 1;
} else {
dp0 = 1;
dp1 = 1;
}
ret = Math.max(ret, dp0);
ret = Math.max(ret, dp1);
}
return ret;
};
golang 解法, 执行用时: 48 ms, 内存消耗: 7 MB, 提交时间: 2023-09-23 00:30:14
func maxTurbulenceSize(arr []int) int {
n := len(arr)
ans := 1
left, right := 0, 0
for right < n-1 {
if left == right {
if arr[left] == arr[left+1] {
left++
}
right++
} else {
if arr[right-1] < arr[right] && arr[right] > arr[right+1] {
right++
} else if arr[right-1] > arr[right] && arr[right] < arr[right+1] {
right++
} else {
left = right
}
}
ans = max(ans, right-left+1)
}
return ans
}
// dp
func maxTurbulenceSize2(arr []int) int {
n := len(arr)
dp := make([][2]int, n)
dp[0] = [2]int{1, 1}
for i := 1; i < n; i++ {
dp[i] = [2]int{1, 1}
if arr[i-1] > arr[i] {
dp[i][0] = dp[i-1][1] + 1
} else if arr[i-1] < arr[i] {
dp[i][1] = dp[i-1][0] + 1
}
}
ans := 1
for i := 0; i < n; i++ {
ans = max(ans, dp[i][0])
ans = max(ans, dp[i][1])
}
return ans
}
// dp 2
func maxTurbulenceSize3(arr []int) int {
ans := 1
n := len(arr)
dp0, dp1 := 1, 1
for i := 1; i < n; i++ {
if arr[i-1] > arr[i] {
dp0, dp1 = dp1+1, 1
} else if arr[i-1] < arr[i] {
dp0, dp1 = 1, dp0+1
} else {
dp0, dp1 = 1, 1
}
ans = max(ans, max(dp0, dp1))
}
return ans
}
func max(a, b int) int { if a > b { return a }; return b }
cpp 解法, 执行用时: 56 ms, 内存消耗: 39.6 MB, 提交时间: 2023-09-23 00:28:46
class Solution {
public:
// 滑动窗口
int maxTurbulenceSize(vector<int>& arr) {
int n = arr.size();
int ret = 1;
int left = 0, right = 0;
while (right < n - 1) {
if (left == right) {
if (arr[left] == arr[left + 1]) {
left++;
}
right++;
} else {
if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
right++;
} else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
right++;
} else {
left = right;
}
}
ret = max(ret, right - left + 1);
}
return ret;
}
// dp[i][0] 为以 arr[i] 结尾，且 arr[i−1]>arr[i] 的「湍流子数组」的最大长度；
// dp[i][1] 为以 arr[i] 结尾，且 arr[i−1]<arr[i]的「湍流子数组」的最大长度。
int maxTurbulenceSize2(vector<int>& arr) {
int n = arr.size();
vector<vector<int>> dp(n, vector<int>(2, 1));
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
dp[i][0] = dp[i - 1][1] + 1;
} else if (arr[i - 1] < arr[i]) {
dp[i][1] = dp[i - 1][0] + 1;
}
}
int ret = 1;
for (int i = 0; i < n; i++) {
ret = max(ret, dp[i][0]);
ret = max(ret, dp[i][1]);
}
return ret;
}
// dp 2
int maxTurbulenceSize3(vector<int>& arr) {
int ret = 1;
int n = arr.size();
int dp0 = 1, dp1 = 1;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
dp0 = dp1 + 1;
dp1 = 1;
} else if (arr[i - 1] < arr[i]) {
dp1 = dp0 + 1;
dp0 = 1;
} else {
dp0 = 1;
dp1 = 1;
}
ret = max(ret, dp0);
ret = max(ret, dp1);
}
return ret;
}
};
java 解法, 执行用时: 5 ms, 内存消耗: 46.8 MB, 提交时间: 2023-09-23 00:27:23
class Solution {
// 滑动窗口
public int maxTurbulenceSize(int[] arr) {
int n = arr.length;
int ret = 1;
int left = 0, right = 0;
while (right < n - 1) {
if (left == right) {
if (arr[left] == arr[left + 1]) {
left++;
}
right++;
} else {
if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
right++;
} else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
right++;
} else {
left = right;
}
}
ret = Math.max(ret, right - left + 1);
}
return ret;
}
// dp[i][0] 为以 arr[i] 结尾，且 arr[i−1]>arr[i] 的「湍流子数组」的最大长度；
// dp[i][1] 为以 arr[i] 结尾，且 arr[i−1]<arr[i]的「湍流子数组」的最大长度。
public int maxTurbulenceSize2(int[] arr) {
int n = arr.length;
int[][] dp = new int[n][2];
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i][1] = 1;
if (arr[i - 1] > arr[i]) {
dp[i][0] = dp[i - 1][1] + 1;
} else if (arr[i - 1] < arr[i]) {
dp[i][1] = dp[i - 1][0] + 1;
}
}
int ret = 1;
for (int i = 0; i < n; i++) {
ret = Math.max(ret, dp[i][0]);
ret = Math.max(ret, dp[i][1]);
}
return ret;
}
// dp 2
public int maxTurbulenceSize3(int[] arr) {
int ret = 1;
int n = arr.length;
int dp0 = 1, dp1 = 1;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
dp0 = dp1 + 1;
dp1 = 1;
} else if (arr[i - 1] < arr[i]) {
dp1 = dp0 + 1;
dp0 = 1;
} else {
dp0 = 1;
dp1 = 1;
}
ret = Math.max(ret, dp0);
ret = Math.max(ret, dp1);
}
return ret;
}
}
java 解法, 执行用时: 6 ms, 内存消耗: 44.9 MB, 提交时间: 2023-09-23 00:24:19
public class Solution {
// 动态规划
public int maxTurbulenceSize(int[] arr) {
int len = arr.length;
if (len < 2) {
return len;
}
// 以 arr[i] 结尾，并且 arr[i - 1] < arr[i] 的湍流子数组的长度
int[] increased = new int[len];
// 以 arr[i] 结尾，并且 arr[i - 1] > arr[i] 的湍流子数组的长度
int[] decreased = new int[len];
increased[0] = 1;
decreased[0] = 1;
int res = 1;
for (int i = 1; i < len; i++) {
if (arr[i - 1] < arr[i]) {
increased[i] = decreased[i - 1] + 1;
decreased[i] = 1;
} else if (arr[i - 1] > arr[i]) {
decreased[i] = increased[i - 1] + 1;
increased[i] = 1;
} else {
increased[i] = 1;
decreased[i] = 1;
}
res = Math.max(res, Math.max(increased[i], decreased[i]));
}
return res;
}
// 双指针
public int maxTurbulenceSize2(int[] arr) {
int len = arr.length;
if (len < 2) {
return len;
}
int left = 0;
int right = 1;
// 为 true 表示 arr[i - 1] < arr[i]
boolean pre = false;
int res = 1;
while (right < len) {
boolean current = arr[right - 1] < arr[right];
if (current == pre) {
left = right - 1;
}
if (arr[right - 1] == arr[right]) {
left = right;
}
right++;
res = Math.max(res, right - left);
pre = current;
}
return res;
}
}