[LeetCode] 978. Longest Turbulent Subarray

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)