擺動序列，也能貪心
擺動序列
力扣題目鏈接：https://leetcode-cn.com/problems/wiggle-subsequence
如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為擺動序列。第一個差(如果存在的話)可能是正數或負數。少于兩個元素的序列也是擺動序列。
例如， [1,7,4,9,2,5] 是一個擺動序列，因為差值 (6,-3,5,-7,3) 是正負交替出現的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零。
給定一個整數序列，返回作為擺動序列的最長子序列的長度。通過從原始序列中刪除一些(也可以不刪除)元素來獲得子序列，剩下的元素保持其原始順序。
示例 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(貪心解法)
本題要求通過從原始序列中刪除一些(也可以不刪除)元素來獲得子序列，剩下的元素保持其原始順序。
相信這么一說嚇退不少同學，這要求最大擺動序列又可以修改數組，這得如何修改呢?
來分析一下，要求刪除元素使其達到最大擺動序列，應該刪除什么元素呢?
用示例二來舉例，如圖所示：
擺動序列
局部最優：刪除單調坡度上的節點(不包括單調坡度兩端的節點)，那么這個坡度就可以有兩個局部峰值。
整體最優：整個序列有最多的局部峰值，從而達到最長擺動序列。
局部最優推出全局最優，并舉不出反例，那么試試貪心!
(為方便表述，以下說的峰值都是指局部峰值)
實際操作上，其實連刪除的操作都不用做，因為題目要求的是最長擺動子序列的長度，所以只需要統計數組的峰值數量就可以了(相當于是刪除單一坡度上的節點，然后統計長度)
這就是貪心所貪的地方，讓峰值盡可能的保持峰值，然后刪除單一坡度上的節點。
本題代碼實現中，還有一些技巧，例如統計峰值的時候，數組最左面和最右面是最不好統計的。
例如序列[2,5]，它的峰值數量是2，如果靠統計差值來計算峰值個數就需要考慮數組最左面和最右面的特殊情況。
所以可以針對序列[2,5]，可以假設為[2,2,5]，這樣它就有坡度了即preDiff = 0，如圖：
.擺動序列1
針對以上情形，result初始為1(默認最右面有一個峰值)，此時curDiff > 0 && preDiff <= 0，那么result++(計算了左面的峰值)，最后得到的result就是2(峰值個數為2即擺動序列長度為2)
C++代碼如下(和上圖是對應的邏輯)：
- 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 = 0; i < nums.size() - 1; i++) {
- curDiff = nums[i + 1] - nums[i];
- // 出現峰值
- if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
- result++;
- preDiff = curDiff;
- }
- }
- return result;
- }
- };
時間復雜度O(n) 空間復雜度O(1)
思路2(動態規劃)
考慮用動態規劃的思想來解決這個問題。
很容易可以發現，對于我們當前考慮的這個數，要么是作為山峰(即nums[i] > nums[i-1])，要么是作為山谷(即nums[i] < nums[i - 1])。
- 設dp狀態dp[i][0]，表示考慮前i個數，第i個數作為山峰的擺動子序列的最長長度
- 設dp狀態dp[i][1]，表示考慮前i個數，第i個數作為山谷的擺動子序列的最長長度
則轉移方程為：
- 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]接到前面某個山峰后面，作為山谷。
初始狀態：
由于一個數可以接到前面的某個數后面，也可以以自身為子序列的起點，所以初始狀態為：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]);
- }
- };
- 時間復雜度O(n^2)
- 空間復雜度O(n)
進階
可以用兩棵線段樹來維護區間的最大值
每次更新dp[i][0]，則在tree1的nums[i]位置值更新為dp[i][0]
每次更新dp[i][1]，則在tree2的nums[i]位置值更新為dp[i][1]
則dp轉移方程中就沒有必要j從0遍歷到i-1，可以直接在線段樹中查詢指定區間的值即可。
- 時間復雜度O(nlogn)
- 空間復雜度O(n)
總結
貪心的題目說簡單有的時候就是常識，說難就難在都不知道該怎么用貪心。
本題大家如果要去模擬刪除元素達到最長擺動子序列的過程，那指定繞里面去了，一時半會拔不出來。
而這道題目有什么技巧說一下子能想到貪心么?
其實也沒有，類似的題目做過了就會想到。
此時大家就應該了解了：保持區間波動，只需要把單調區間上的元素移除就可以了。
