978. 最长湍流子数组--leetcode --c#

题目描述:

当 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:

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


示例 2:

输入:[4,8,12,16]
输出:2


示例 3:

输入:[100]
输出:1

 

提示:


    1 <= A.length <= 40000
    0 <= A[i] <= 10^9

解题思路:最大滑动窗口(双指针)算法。

把A数组看成一排数,前边的指针一步一步往前走(步长为1),此时两指针间形成窗口。窗口长度(n-m+1)。记录到maxSize。直到走到头,找到最大size。

C#代码如下:

       public static int MaxTurbulenceSize(int[] A)
        {
            int maxSize = 1;
            int len = A.Length;
            int lastFlag = 0;//记录上次相邻元素间的大小情况。 1:k+1>k  ; 0: K+1 == k ; -1: k+1<k
            for (int i = 1, j = 0; i < len; i++)//最大滑动窗口(双指针)算法:i前边的指针,j后边的指针,i++, j分情况往前走。窗口大小为i - j + 1
            {
                int flag = Math.Sign(A[i] - A[i - 1]);// 当前减去上一个,然后用符号函数处理
                if (flag == 0)//当前等于上一个
                {
                    maxSize = Math.Max(maxSize, i - j);// 窗口大小为(i-1) - j + 1 = i-j  注:因为i不满组情况,所以是i-1
                    j = i; //把后边指针更新到当前位置
                    lastFlag = 0;//重设为0
                }
                else if (flag + lastFlag == 0)//说明符合题意:本次相邻两数大小情况和前一次相反
                {
                    lastFlag = flag;//更新标记
                    if (i == len - 1) maxSize = Math.Max(maxSize, i - j + 1);//如果遍历完,窗口大小为i - j + 1
                }
                else //说明两次大小情况相同,不符合题意
                {
                    maxSize = Math.Max(maxSize, i - j);
                    j = i - 1; //把后边指针更新到当前位置。窗口起点应该是i-1
                    lastFlag = flag;//更新标记
                }
            }
            return maxSize;
        }

上一篇:队列


下一篇:数据结构初级~~~~赵磊