旺崽的博客

要么天赋异禀，要么天道酬勤

0%

LeetCode 978 最长湍流子数组

发表于 分类于 Valine：

题目链接

当 A 的子数组 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 的最大湍流子数组的长度。

示例 1：

1
2
3
输入：[9,4,2,10,7,8,8,1,9]
输出：5
解释：(A[1] > A[2] < A[3] > A[4] < A[5])

示例 2：

1
2
输入：[4,8,12,16]
输出：2

示例 3：

1
2
输入：[100]
输出：1

思维~
官方题解有滑窗，有 DP，但是我另辟蹊径，用一种纯思维的方式，首先求两两数的差值，存入 diff 数组：

  • arr[i]>arr[i+1]，存入 $1$
  • arr[i]<arr[i+1]，存入 $-1$
  • arr[i]=arr[i+1]，存入 $0$

求得这个差值数组之后，我们就所有找的最大长度，无非就是求 $1,-1,\cdots,-1，1$ 序列的最大长度，设一个 $mx$ 变量维护最大值即可，对某一位置 $i$ 判断下面两种情况：

  • diff[i]=0，此时必须把 mx 置 0，因为差值为 0 时最大长度为 1
  • diff[i]≠0，若 diff[i]+diff[i+1]=0，mx++；若 diff[i]+diff[i+1]≠0，把 mx 置 1，因为差值不为 0 时的最大长度为 2

每次循环 ans=max(ans,mx+1)，因为 mx 个差值对应 mx+1 个数，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxTurbulenceSize(vector<int> &arr) {
        if (arr.size() == 1) return 1;
        vector<int> diff;
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr[i] > arr[i + 1]) diff.emplace_back(1);
            else if (arr[i] < arr[i + 1]) diff.emplace_back(-1);
            else diff.emplace_back(0);
        }
        int ans = (diff.front() ? 2 : 1), mx = (diff.front() ? 1 : 0);
        for (int i = 1; i < diff.size(); i++) {
            if (!diff[i]) mx = 0;
            else {
                if (diff[i] + diff[i - 1] == 0) mx++;
                else mx = 1;
            }
            ans = max(ans, mx + 1);
        }
        return ans;
    }
};