978. Longest Turbulent Subarray

Given an integer array arr, return  the length of a maximum size turbulent subarray of  arr.

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

More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:

  • For i <= k < j:
    • arr[k] > arr[k + 1] when k is odd, and
    • arr[k] < arr[k + 1] when k is even.
  • Or, for i <= k < j:
    • arr[k] > arr[k + 1] when k is even, and
    • arr[k] < arr[k + 1] when k is odd.

Example 1:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

Example 2:

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

Example 3:

Input: arr = [100]
Output: 1

Constraints:

  • 1 <= arr.length <= 4 * 104
  • 0 <= arr[i] <= 109

这道题给了一个数组,定义一种湍流子数组,即数字增减交替,就是先增大再减小再增大等交替进行,或者是先减小再增大再减小等交替进行的。现在让找出最长的湍流子数组,并返回长度。首先最无脑的暴力搜索就是遍历所有的子数组,并判断是否是湍流数组,这样太不高效了,有点不尊重 OJ 的感觉,估计不会给过。毕竟是道 Medium 题,总得给点面子吧,那就来想一下,我们并不知道湍流子数组的起点在哪,也不知道它到底是先增大还是先减小,这样的话其实每个位置都有可能是一个湍流数组的起点或终点,就按终点来考虑,每个位置都代表一种状态,而且这道题又是求极值的问题,那么该什么方法是不是就呼之欲出了,来~大声地告诉博主,用什么方法?对了,就是动态规划 Dynamic Programming,首先来想怎么定义 dp 数组,要求的是湍流子数组的长度,那么 dp 值代表的含义应该也是长度。又因为每个位置都可能是个湍流子数组的终点,并且末尾数字可能是下降或者上升,有两种状态,可以用一个二维 dp 数组,也可以用两个一维数组 dec 和 inc 来表示,这里 dec[i] 表示湍流数组的长度,同时其末尾是数字是 arr[i] 且是下降的,同理,inc[i] 表示湍流数组的长度,同时其末尾是数字是 arr[i] 且是上升的。数组定义好了,下面是就是找状态转移方程了,其实也不难,当前状态跟前一个状态息息相关,首先要比较当前数字和前一个数字的大小关系,若前一个数字大于当前数字,则表示下降的关系,则可以更新 dec[i] 为 inc[i-1] + 1,反之,若前一个数字小于当前数字,则表示上升的关系,则可以更新 inc[i] 为 dec[i-1] + 1。每次更新完一个位置,从 dec[i] 和 inc[i] 中找出最大的位置,用来更新结果 res 即可,参见代码如下:

解法一:

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int res = 1, n = arr.size();
        vector<int> dec(n, 1), inc(n, 1);
        for (int i = 1; i < n; ++i) {
            if (arr[i - 1] > arr[i]) {
                dec[i] = inc[i - 1] + 1;            
            } else if (arr[i - 1] < arr[i]) {
                inc[i] = dec[i - 1] + 1;
            }
            res = max(res, max(dec[i], inc[i]));
        }
        return res;
    }
};

我们可以进一步的更新空间复杂度,因为当前状态仅仅依赖前一个状态,所以没有必要保留所有位置的状态,就只有两个变量就可以了,不过要注意的是别忘了及时的将 inc 或 dec 重置为1,当相邻的两个数字相同时,两者还要同时重置1,参见代码如下:

解法二:

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int res = 1, n = arr.size(), inc = 1, dec = 1;
        for (int i = 1; i < n; ++i) {
            if (arr[i] < arr[i - 1]) {
                dec = inc + 1;
                inc = 1;
            } else if (arr[i] > arr[i - 1]) {
                inc = dec + 1;
                dec = 1;
            } else {
                inc = 1;
                dec = 1;
            }
            res = max(res, max(inc, dec));
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/978

类似题目:

Maximum Subarray

参考资料:

https://leetcode.com/problems/longest-turbulent-subarray/

https://leetcode.com/problems/longest-turbulent-subarray/discuss/221935/Java-O(N)-time-O(1)-space

https://leetcode.com/problems/longest-turbulent-subarray/discuss/221929/C%2B%2BJava-6-lines-flip-the-sign

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation