leetcode【978-最长湍流子数组】思考、优化、改进

淩亂°似流年 2022-10-29 03:29 140阅读 0赞

声 明 ： 该 系 列 是 我 的 随 笔 ， 会 记 录 一 些 刷 题 的 感 受 ， 思 路 。 文 章 难 免 有 错 误 或 语 句 不 够 严 谨 ， 欢 迎 指 正 。 \\color\{\#FF0000\}\{声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。 \} 声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。  
 如 果 读 者 关 于 这 道 题 有 其 他 疑 问 ， 也 欢 迎 在 评 论 区 和 我 讨 论 我 会 及 时 回 复 ， 互 相 进 步 ， 谢 谢 ！ \\color\{\#FF0000\}\{如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！\} 如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！

# 一、题目&示例 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjI0MDMw_size_16_color_FFFFFF_t_70]

# 二、分析 #

初次看题干很容易想到DP，设置dp\[i\]表示以i结束的最大湍流子数组长度  
状态转移方程：  
if(上个波浪是上升波浪&&arr\[i-1\]>arr\[i\])  
   dp\[i\] = dp\[i+1\]  
if(上个波浪是下降波浪&&arr\[i-1\]<arr\[i\])  
   dp\[i\] = dp\[i+1\]

初始值：  
全设置为1;

对于如何判断上升还是下降波：  
设置一个isRising数组（-1,0，1）  
其中-1表示上一个是下降波  
其中0表示上一个和这一个值相同  
其中-1表示上一个是上升波

# 三、代码 #

class Solution { 
    public:
    int maxTurbulenceSize(vector<int>& arr) { 
        /* Initialize */
        int  isRising = -2;           //bool flag 判断波浪形状
        int  n        = arr.size(); //样本容量
        vector<int > dp(n,2);//dp[i] :以i结束的最大湍流子数组长度
        //some special example
        if(n==1)
            return 1;
        /* main */
        for(int i = 1;i != n ;i++)
        { 
            //Update dp[i]
            if(isRising == 1&&arr[i-1]>arr[i])
                dp[i] = dp[i-1]+1;
            else if(isRising == -1&&arr[i-1]<arr[i])
                dp[i] = dp[i-1]+1;
            else if(arr[i-1]!=arr[i])
                dp[i] = 2;
            //Update isRising
            if(arr[i-1]>arr[i])
                isRising = -1;
            if(arr[i-1]<arr[i])
                isRising = 1;
            if(arr[i-1]==arr[i])
                isRising = 0;
        }
        //Find max
        int max = dp[0];
        for(int i = 0;i != n; i++)
        if(max<dp[i])
            max = dp[i];
        return max;
    }
    
    };

值得注意的是以下几点：  
1.注意n=1时候的特殊情况，应当单独处理  
2.对于arr\[i\]==arr\[i+1\]的情况一定要单独处理，大体上的方法有两种，一种是dp数组初始化为1，碰见相等的不变，碰见不相等的变为2。第二章方法是将dp数组初始化为2，单独处理相等情况  
3.官方题解使用两个dp数组来分别表示上升和下降，我个人认为稍微麻烦一些，也不容易想，就不再解析官方题解。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjI0MDMw_size_16_color_FFFFFF_t_70]: /images/20221024/b74f250e37a7493a9bf395cd4ef2a6dc.png