[Day 10] Leetcode 978. Longest Turbulent Subarray (C++)

前言

今天下班买到饮料心满意足，今日的挑战是medium，perfect！题目在这边：978. Longest Turbulent Subarray；简单来说，就是要找到vector中相邻元素差值是相反的连续最长数列。废话不多说直接开始解题。

想法

这个题目乍看下去，就觉得可以用遍历一次O(n)解决，可以很greedy的来完成。毕竟，其实题目的本质就跟找什麽最常连续递增数列差不多，直接一路检查下去，如果断了就重新计算就好啦！然後同步一直更新目前最长数列的值。
不过看到这个题目类型的时候，也有隐隐约约的感觉可能也有一路是想用DP解法，看了一下题目下面的tag果然有dynamic programmingXD 但这题的题目很单纯，杀鸡焉用牛刀，可以greedy就直接下去就好啦！不过也可以思考一下DP怎麽解，训练一下DP敏锐度，毕竟当题目复杂起来，DP还是很好用的。
不过这题我一开始也有小小地掉个坑，例如，我本来是这样写的：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        // greedy to find the current maxima
        if(arr.size()<=2){
            return arr.size();
        }
        int curL=2;
        int ans=1;
        int curS=bool(arr[1]>arr[0]);
        for(int i=2;i<arr.size();++i){// from the second one to compute the difference
            if (curS != arr[i]>arr[i-1]){
                ++curL;
            }else
            {
                curL=2;
            }
            curS = (arr[i]>arr[i-1]);
            ans = max(ans, curL);    
        }
        return ans;
    }
};

看一下，发现问题了吗？
没错，忘记考虑相邻元素是相等的情况了！本来很直觉地想说，看题目给的example，只有一个的话答案就是1，或两个就是2，但像[9,9]的情况答案是1才对！因为相邻两者=的情况就不属於有方向的情况。
考虑到这点，做了一些修改，可能也有更精简的写法，就可以再看着改罗。

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        // greedy to find the current maxima
        if(arr.size()==1){
            return 1;
        }
        if(arr.size()==2){
            if(arr[1]!=arr[0]){
                return 2;
            }
        }
        int curL=1;
        if(arr[1]!=arr[0]){
            curL=2;
        }
        int ans=1;
        int curS=bool(arr[1]>arr[0]);
        for(int i=2;i<arr.size();++i){// from the second one to compute the difference
            if (curS != arr[i]>arr[i-1] && arr[i]!=arr[i-1]){
                ++curL;
            }else if(arr[i]!=arr[i-1])// same way
            {
                curL=2;
            }else// consider equal condition
            {
                curL=1;
            }
            curS = (arr[i]>arr[i-1]);
            ans = max(ans, curL);    
        }
        return ans;
    }
};

时间复杂度是O(n)复杂度不用怀疑，至於空间则是O(1)，大概只需要存curL、ans、curS这几个变数而已，不会因为题目的数列长度不同而增加。
最後再来讲一下前面提到的DP作法，本来打完跳到别的页面没存到档再来重打一次= =
经典DP就是把问题缩小到只考虑当下状况+前面状况就好，所以可以用一个n长度的vector来存必定包含该格的最长数列，更新方法就是先填入第0格是1，第1格如果第零个元素跟第一个元素不同就是2，跟第一个元素相同相同就是1，并记录方向，接下来只要考虑当下元素的方向是否跟前者不同且元素不可相等，不同该格就=前一格+1，相同该格就=2，元素相等则是1，最後再去找里面的最大值；上面的作法时间复杂度一样是O(n)，但空间复杂度也是O(n)，当然空间复杂度也可以优化成只存previousState就也是O(1)，不过就是比较有系统化的解法~

结语

今天文章内容应该有比较充实吧！重打了一次Q