擺動(dòng)序列，也能貪心

作者：程序員Carl 2021-11-11 11:31:54

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

[[434526]]

擺動(dòng)序列

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

例如， [1,7,4,9,2,5] 是一個(gè)擺動(dòng)序列，因?yàn)椴钪?(6,-3,5,-7,3) 是正負(fù)交替出現(xiàn)的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動(dòng)序列，第一個(gè)序列是因?yàn)樗那皟蓚€(gè)差值都是正數(shù)，第二個(gè)序列是因?yàn)樗淖詈笠粋€(gè)差值為零。

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

示例 1:

輸入: [1,7,4,9,2,5]
輸出: 6
解釋: 整個(gè)序列均為擺動(dòng)序列。

示例 2:

輸入: [1,17,5,10,13,15,10,5,16,8]
輸出: 7
解釋: 這個(gè)序列包含幾個(gè)長(zhǎng)度為 7 擺動(dòng)序列，其中一個(gè)可為[1,17,10,13,10,16,8]。

示例 3:

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

思路1(貪心解法)

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

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

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

用示例二來(lái)舉例，如圖所示：

擺動(dòng)序列

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

整體最優(yōu)：整個(gè)序列有最多的局部峰值，從而達(dá)到最長(zhǎng)擺動(dòng)序列。

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

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

實(shí)際操作上，其實(shí)連刪除的操作都不用做，因?yàn)轭}目要求的是最長(zhǎng)擺動(dòng)子序列的長(zhǎng)度，所以只需要統(tǒng)計(jì)數(shù)組的峰值數(shù)量就可以了(相當(dāng)于是刪除單一坡度上的節(jié)點(diǎn)，然后統(tǒng)計(jì)長(zhǎng)度)

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

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

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

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

.擺動(dòng)序列1

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

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

class Solution { 
public: 
    int wiggleMaxLength(vector<int>& nums) { 
        if (nums.size() <= 1) return nums.size(); 
        int curDiff = 0; // 當(dāng)前一對(duì)差值 
        int preDiff = 0; // 前一對(duì)差值 
        int result = 1;  // 記錄峰值個(gè)數(shù)，序列默認(rèn)序列最右邊有一個(gè)峰值 
        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; 
    } 
};

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

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

考慮用動(dòng)態(tài)規(guī)劃的思想來(lái)解決這個(gè)問(wèn)題。

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

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

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

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

初始狀態(tài)：

由于一個(gè)數(shù)可以接到前面的某個(gè)數(shù)后面，也可以以自身為子序列的起點(diǎn)，所以初始狀態(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]); 
    } 
};