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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了978. 最长湍流子数组--leetcode --c#，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2151字，纯文字阅读大概需要4分钟。

内容图文

题目描述：

当 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;
        }

内容总结

以上是互联网集市为您收集整理的978. 最长湍流子数组--leetcode --c#全部内容，希望文章能够帮你解决978. 最长湍流子数组--leetcode --c#所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端