題目網址：https://leetcode.cn/problems/wiggle-subsequence/

題意：如果連續數字之間的差值在正數和負數之間交替, 則該 subsequence 稱為 Wiggle Subsequence。第一個差值（如果存在的話）可能是正數 or 負數。僅有一個元素 or 兩個不相等元素的 subsequence 也被視作 Wiggle Subsequence。

  • e.g. [1, 7, 4, 9, 2, 5] 是一個 Wiggle Subsequence, 因為差值 (6, -3, 5, -7, 3) 是正負交替出現的。

subsequence 可以通過從原 array 中刪除一些（也可以不刪除）元素來獲得, 剩下的元素保持其原先順序。

給一整數 array nums, 返回 nums 中 最長 Wiggle Subsequence 的長度。

進階：設計 $O(n)$ time 的演算法。

Solution 1：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
  • up[i] 代表 nums[1:i] 中以某一元素為結尾, 且「結尾上升」的最長 wiggle subsequence 之長度
  • down[i] 代表 nums[1:i] 中以某一元素為結尾, 且「結尾下降」的最長 wiggle subsequence 之長度

2. 得到狀態轉移方程：

  • 若 nums[i] > nums[i - 1]：可以選出更長的結尾上升 wiggle subsequence, 但是結尾下降 wiggle subsequence 則無法選出更長的
    • up[i] = max(up[i - 1], down[i - 1] + 1)
    • down[i] = down[i - 1]
  • 若 nums[i] < nums[i - 1]：可以選出更長的結尾下降 wiggle subsequence, 但是結尾上升 wiggle subsequence 則無法選出更長的
    • up[i] = up[i - 1]
    • down[i] = max(down[i - 1], up[i - 1] + 1)
  • 若 nums[i] == nums[i - 1]：則結尾上升、下降 wiggle subsequence 都無法選出更長的
    • up[i] = up[i - 1]
    • down[i] = down[i - 1]

3. 初始化：

  • 當沒有元素時, up[0] = down[0] = 0
  • 當只有一個元素時, 也會被視作為 wiggle subsequence, 故 up[1] = down[1] = 1

4. 你可能會問：up[i] 和 down[i] 只記錄 nums[1:i] 中結尾上升、下降最長 wiggle subsequence 的長度, 又沒紀錄 subsequence 的結尾 end, 為什麼可以透過比較 nums[i] 和 nums[i - 1] 來決定狀態的轉移？不是應該比較 nums[i] 和 end 嗎？

  • 當 nums[i] > nums[i - 1] 時：

    • 假設 down[i - 1] 的結尾最大 idx j 為 i - 1, 則 nums[j] 剛好遇到上升元素

      ➔ up[i] = down[i - 1] + 1

    • 假設 down[i - 1] 的結尾最大 idx j 小於 i - 1, 則 nums[j] < nums[i - 1]。因為如果 nums[j] > nums[i - 1], 則 nums[i - 1] 可替換 nums[j] 成為結尾, 但實際上 j < i - 1, 故矛盾

      ➔ 若 j < i - 1, 則 nums[j] < nums[i - 1]

      • 且 nums[j:(i-1)] 必為遞增的。因為若非遞增, 則會產生波動, 並產生新的拐點 k 使得 down[j] < down[k], 這與之前假設的 down[i - 1] 的結尾最大 idx j 矛盾

        ➔ down[j:(i-1)] 皆等於 down[j], 因為 nums[j:(i-1)] 必為遞增的

      ➔ 當 j < i - 1 且 nums[i] > nums[i - 1], 依然滿足 up[i] = down[i - 1] + 1

  • nums[i] < nums[i - 1]：同理

  • 當 nums[i] == nums[i - 1]：新元素無法用於任何 subsequence, 故保持不變

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        const int n = nums.size();

        if (n < 2) {
            return n;
        }

        vector<int> up(n + 1, 0), down(n + 1, 0);

        nums.emplace(nums.begin(), 0);
        up[1] = 1, down[1] = 1;

        for (int i = 2; i <= n; ++i) {
            if (nums[i] > nums[i - 1]) {
                up[i] = max(up[i - 1], down[i - 1] + 1);
                down[i] = down[i - 1];
            } else if (nums[i] < nums[i - 1]) {
                up[i] = up[i - 1];
                down[i] = max(down[i - 1], up[i - 1] + 1);
            } else {
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }

        return max(up.back(), down.back());
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ up, down

Solution 2：

想法：改進 Solution 1, 由於 up[i], down[i] 只會用到 i - 1 的狀態, 因此只須記住上一次的狀態即可, 根本不需要開到 $O(n)$ space。由於 up, down 記住了上一次的狀態, 所以原先在 Solution 1 的 for loop 中沒有更新的部分在 Solution 2 就不用寫出來, e.g. up[i] = up[i - 1], down[i] = down[i - 1], 只需要寫更新的部分即可

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        const int n = nums.size();

        if (n < 2) {
            return n;
        }

        int up = 1, down = 1;
        nums.emplace(nums.begin(), 0);

        for (int i = 2; i <= n; ++i) {
            if (nums[i] > nums[i - 1]) {
                up = max(up, 1 + down);
            } else if (nums[i] < nums[i - 1]) {
                down = max(down, 1 + up);
            }
        }

        return max(up, down);
    }
};

  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間

Solution 3：

想法：利用 Greedy, 盡可能地加入拐點。用 diff 紀錄當前的斜率, prevDiff 紀錄上一次的斜率, 只要 diff != prevDiff 就把當前的點加入。若 diff 和 prevDiff 是同個趨勢 or nums[i] == nums[i - 1], 則不加入

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        const int n = nums.size();

        if (n < 2) {
            return n;
        }

        int res = 1, diff = 0; // 初始斜率為 0
        nums.emplace(nums.begin(), 0);

        for (int i = 2; i <= n; ++i) {
            const int prevDiff = diff;

            if (nums[i] > nums[i - 1]) {
                diff = 1;
            } else if (nums[i] < nums[i - 1]) {
                diff = -1;
            } else {
                diff = prevDiff;
            }

            if (diff != prevDiff) {
                ++res;
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間