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

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

來分析一下，要求刪除元素使其達到最大擺動序列，應該刪除什么元素呢？

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

「局部最優：刪除單調坡度上的節點（不包括單調坡度兩端的節點），那么這個坡度就可以有兩個局部峰值」。

「整體最優：整個序列有最多的局部峰值，從而達到最長擺動序列」。

局部最優推出全局最優，并舉不出反例，那么試試貪心！

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

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

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

本題代碼實現中，還有一些技巧，例如統計峰值的時候，數組最左面和最右面是最不好統計的。

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

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

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

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

保持區間波動，只需要把單調區間上的元素移除就可以了。

總結

以上是生活随笔為你收集整理的摆动序列-的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。