【LeetCode】最长湍流子数组

HQ数字卡

关注

发布于: 2021 年 02 月 08 日

题目

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

代码

public class DayCode {    public static void main(String[] args) {        int[] arr = new int[]{9,4,2,10,7,8,8,1,9};        int ans = new DayCode().maxTurbulenceSize(arr);        System.out.println("ans is " + ans);    }
    /**     * https://leetcode-cn.com/problems/longest-turbulent-subarray/     * @param arr     * @return     * 时间复杂度O(n)     * 空间复杂度O(n)     */    public int maxTurbulenceSize(int[] arr) {        int n = arr.length;        if (n < 2) {            return n;        }        int ans = 1;        int[] increased = new int[n];        int[] decreased = new int[n];        increased[0] = 1;        decreased[0] = 1;        for (int i = 1; i < n; 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 {                decreased[i] = 1;                increased[i] = 1;            }            ans = Math.max(ans, Math.max(increased[i], decreased[i]));        }        return ans;    }}

复制代码

总结

照例，这个题目应该用滑动窗口来解。自己写完之后，还是觉的 DP 更加好理解一些。
上述方法还可以继续优化，空间复杂度可以优化成 O(1)，decreased，increased 可以用一个变量来记录状态值，从而优化空间复杂度。

发布于: 2021 年 02 月 08 日阅读数: 10

原文链接:【http://xie.infoq.cn/article/9066b5a22a529900d919e7b08】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】最长湍流子数组

题目

代码

总结

HQ数字卡

评论