[[434526]]

擺動序列

力扣題目鏈接：https://leetcode-cn.com/problems/wiggle-subsequence

如果連續(xù)數(shù)字之間的差嚴格地在正數(shù)和負數(shù)之間交替，則數(shù)字序列稱為擺動序列。第一個差(如果存在的話)可能是正數(shù)或負數(shù)。少于兩個元素的序列也是擺動序列。

例如， [1,7,4,9,2,5] 是一個擺動序列，因為差值 (6,-3,5,-7,3) 是正負交替出現(xiàn)的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數(shù)，第二個序列是因為它的最后一個差值為零。

給定一個整數(shù)序列，返回作為擺動序列的最長子序列的長度。通過從原始序列中刪除一些(也可以不刪除)元素來獲得子序列，剩下的元素保持其原始順序。

示例 1:

• 輸入: [1,7,4,9,2,5]
• 輸出: 6
• 解釋: 整個序列均為擺動序列。

示例 2:

• 輸入: [1,17,5,10,13,15,10,5,16,8]
• 輸出: 7
• 解釋: 這個序列包含幾個長度為 7 擺動序列，其中一個可為[1,17,10,13,10,16,8]。

示例 3:

• 輸入: [1,2,3,4,5,6,7,8,9]
• 輸出: 2

思路1(貪心解法)

本題要求通過從原始序列中刪除一些(也可以不刪除)元素來獲得子序列，剩下的元素保持其原始順序。

相信這么一說嚇退不少同學，這要求最大擺動序列又可以修改數(shù)組，這得如何修改呢?

來分析一下，要求刪除元素使其達到最大擺動序列，應(yīng)該刪除什么元素呢?

用示例二來舉例，如圖所示：

擺動序列

局部最優(yōu)：刪除單調(diào)坡度上的節(jié)點(不包括單調(diào)坡度兩端的節(jié)點)，那么這個坡度就可以有兩個局部峰值。

整體最優(yōu)：整個序列有最多的局部峰值，從而達到最長擺動序列。

局部最優(yōu)推出全局最優(yōu)，并舉不出反例，那么試試貪心!

(為方便表述，以下說的峰值都是指局部峰值)

實際操作上，其實連刪除的操作都不用做，因為題目要求的是最長擺動子序列的長度，所以只需要統(tǒng)計數(shù)組的峰值數(shù)量就可以了(相當于是刪除單一坡度上的節(jié)點，然后統(tǒng)計長度)

這就是貪心所貪的地方，讓峰值盡可能的保持峰值，然后刪除單一坡度上的節(jié)點。

本題代碼實現(xiàn)中，還有一些技巧，例如統(tǒng)計峰值的時候，數(shù)組最左面和最右面是最不好統(tǒng)計的。

例如序列[2,5]，它的峰值數(shù)量是2，如果靠統(tǒng)計差值來計算峰值個數(shù)就需要考慮數(shù)組最左面和最右面的特殊情況。

所以可以針對序列[2,5]，可以假設(shè)為[2,2,5]，這樣它就有坡度了即preDiff = 0，如圖：

.擺動序列1

針對以上情形，result初始為1(默認最右面有一個峰值)，此時curDiff > 0 && preDiff <= 0，那么result++(計算了左面的峰值)，最后得到的result就是2(峰值個數(shù)為2即擺動序列長度為2)

C++代碼如下(和上圖是對應(yīng)的邏輯)：

class Solution { 
public: 
    int wiggleMaxLength(vector<int>& nums) { 
        if (nums.size() <= 1) return nums.size(); 
        int curDiff = 0; // 當前一對差值 
        int preDiff = 0; // 前一對差值 
        int result = 1;  // 記錄峰值個數(shù)，序列默認序列最右邊有一個峰值 
        for (int i = 0; i < nums.size() - 1; i++) { 
            curDiff = nums[i + 1] - nums[i]; 
            // 出現(xiàn)峰值 
            if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) { 
                result++; 
                preDiff = curDiff; 
            } 
        } 
        return result; 
    } 
}; 

時間復(fù)雜度O(n) 空間復(fù)雜度O(1)

思路2(動態(tài)規(guī)劃)

考慮用動態(tài)規(guī)劃的思想來解決這個問題。

很容易可以發(fā)現(xiàn)，對于我們當前考慮的這個數(shù)，要么是作為山峰(即nums[i] > nums[i-1])，要么是作為山谷(即nums[i] < nums[i - 1])。

• 設(shè)dp狀態(tài)dp[i][0]，表示考慮前i個數(shù)，第i個數(shù)作為山峰的擺動子序列的最長長度
• 設(shè)dp狀態(tài)dp[i][1]，表示考慮前i個數(shù)，第i個數(shù)作為山谷的擺動子序列的最長長度

則轉(zhuǎn)移方程為：

• dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，表示將nums[i]接到前面某個山谷后面，作為山峰。
• dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，表示將nums[i]接到前面某個山峰后面，作為山谷。

初始狀態(tài)：

由于一個數(shù)可以接到前面的某個數(shù)后面，也可以以自身為子序列的起點，所以初始狀態(tài)為：dp[0][0] = dp[0][1] = 1。

C++代碼如下：

class Solution { 
public: 
    int dp[1005][2]; 
    int wiggleMaxLength(vector<int>& nums) { 
        memset(dp, 0, sizeof dp); 
        dp[0][0] = dp[0][1] = 1; 
 
        for (int i = 1; i < nums.size(); ++i) 
        { 
            dp[i][0] = dp[i][1] = 1; 
 
            for (int j = 0; j < i; ++j) 
            { 
                if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1); 
            } 
 
            for (int j = 0; j < i; ++j) 
            { 
                if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1); 
            } 
        } 
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]); 
    } 
}; 

• 時間復(fù)雜度O(n^2)
• 空間復(fù)雜度O(n)

進階

可以用兩棵線段樹來維護區(qū)間的最大值

每次更新dp[i][0]，則在tree1的nums[i]位置值更新為dp[i][0]

每次更新dp[i][1]，則在tree2的nums[i]位置值更新為dp[i][1]

則dp轉(zhuǎn)移方程中就沒有必要j從0遍歷到i-1，可以直接在線段樹中查詢指定區(qū)間的值即可。

• 時間復(fù)雜度O(nlogn)
• 空間復(fù)雜度O(n)

總結(jié)

貪心的題目說簡單有的時候就是常識，說難就難在都不知道該怎么用貪心。

本題大家如果要去模擬刪除元素達到最長擺動子序列的過程，那指定繞里面去了，一時半會拔不出來。

而這道題目有什么技巧說一下子能想到貪心么?

其實也沒有，類似的題目做過了就會想到。

此時大家就應(yīng)該了解了：保持區(qū)間波動，只需要把單調(diào)區(qū)間上的元素移除就可以了。