978. Longest Turbulent Subarray

川长思鸟来 2022-01-15 06:51 108阅读 0赞

[为什么80%的码农都做不了架构师？>>> ][80_]  ![hot3.png][]

用二维数组 B来记录之前比较的长度

public int maxTurbulenceSize(int[] A) {
            if (A == null || A.length == 0) return 0;
            if (A.length == 1) return 1;
            int res = 0;
            int[][] B = new int[A.length][2];
            B[0][1] = B[0][0] = 1;
            for (int i = 1; i < A.length; i++) {
                if (A[i - 1] > A[i]) {
    		// A[i-2] < A[i-1] > A[i]
    		// 即 B[i-1][1] = A[i-1]>A[i-2] 的长度
                    B[i][0] = B[i - 1][1] + 1;
                    B[i][1] = 1;
                } else if (A[i - 1] < A[i]) {
                    B[i][0] = 1;
    		// A[i-2] > A[i-1] < A[i]
    		// 即 B[i-1][0] = A[i-1]<A[i-2] 的长度
                    B[i][1] = B[i - 1][0] + 1;
                }else{
    		// A[i-1] = A[i]，无法延长
                    B[i][0] = B[i][1] = 1;
                }
                res = Math.max(res, Math.max(B[i][0],B[i][1]));
            }
            for(int[] a:B) {
                System.out.println(Arrays.toString(a));
            }
            return res;
        }

因为B数组前面的数据都没有用到，所以可以优化成类似: [https://leetcode.com/problems/longest-turbulent-subarray/discuss/221935/Java-O(N)-time-O(1)-space][https_leetcode.com_problems_longest-turbulent-subarray_discuss_221935_Java-O_N_-time-O_1_-space] 的代码

转载于:https://my.oschina.net/reter/blog/3044868

[80_]: https://my.oschina.net/u/2663968/blog/3051541
[hot3.png]: /images/20220115/be3ec97e6cc5452d94e51f057cd750da.png
[https_leetcode.com_problems_longest-turbulent-subarray_discuss_221935_Java-O_N_-time-O_1_-space]: https://leetcode.com/problems/longest-turbulent-subarray/discuss/221935/Java-O%28N%29-time-O%281%29-space