376. 摆动序列

发表于 分类于 阅读次数： Waline： 本文字数： 2.3k 阅读时长 ≈ 8 分钟

考点

  • 状态机DP
  • 贪心

思路

题意简述

给定一个整数数组 nums，求一个最长子序列（不要求连续），使得相邻元素的差值满足：

  • 绝对值 > 0（差值不能为 0）
  • 符号正负交替：+ - + - + ... 或 - + - + - ...

单个元素也视为合法的摆动序列，长度为 1。

一、状态机 DP 解法（O(n²)）

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    const int maxn = 1e3 + 5;
    int wiggleMaxLength(vector<int>& nums) {
        int f[maxn][2];
        f[1][0] = f[1][1] = 1;
        int res = 1;
        for (int i = 2; i <= nums.size(); ++i) {
            f[i][0] = f[i][1] = 1;
            for (int l = i - 1; l >= 1; --l) {
                if (nums[i - 1] > nums[l - 1])
                    f[i][0] = max(f[i][0], f[l][1] + 1);
                else if (nums[i - 1] < nums[l - 1])
                    f[i][1] = max(f[i][1], f[l][0] + 1);
            }
            res = max(res, max(f[i][0], f[i][1]));
        }
        return res;
    }
};

下标采用 1-based，nums[i - 1] 对应 DP 的第 i 个位置。

1. 状态定义

设 n = nums.size()，对于 1 ≤ i ≤ n：

  • f[i][0]： 以第 i 个元素结尾，最后一段差值为正（上升） 的最长摆动子序列长度
  • f[i][1]： 以第 i 个元素结尾，最后一段差值为负（下降） 的最长摆动子序列长度

注意： 这里“最后一段差值为正”意思是：

1
2
... nums[l-1], nums[i-1]
其中 nums[i-1] - nums[l-1] > 0

“最后一段差值为负”同理。

2. 初始值设计

对于只有一个元素 nums[0] 的情况：

1
2
f[1][0] = 1
f[1][1] = 1

理由：

  • 单个元素本质上还没有“差值方向”
  • 但为了后续转移方便，我们约定：
    • 它既可以作为“上升结尾”的起点
    • 也可以作为“下降结尾”的起点
  • 所以两个状态都设为 1：
1
第 1 个元素单独选出来，长度都是 1

3. 状态转移方程

对每一个 i（从 2 到 n），以 nums[i-1] 为结尾，尝试接在前面某个 nums[l-1] 后面：

1
1 <= l < i

我们枚举所有这样的 l，并根据 nums[i-1] 和 nums[l-1] 的大小关系转移。

3.1 形成正差（上升）

如果：

1
nums[i-1] > nums[l-1]

那么差值为正，我们希望最后一段差为正，所以：

  • 前一段必须是负差结尾，即用 f[l][1]
  • 接上当前元素 nums[i-1]，长度加 1

转移：

1
f[i][0] = max(f[i][0], f[l][1] + 1)

3.2 形成负差（下降）

如果：

1
nums[i-1] < nums[l-1]

那么差值为负，我们希望最后一段差为负，所以：

  • 前一段必须是正差结尾，即用 f[l][0]
  • 接上当前元素 nums[i-1]，长度加 1

转移：

1
f[i][1] = max(f[i][1], f[l][0] + 1)

3.3 相等情况

如果：

1
nums[i-1] == nums[l-1]

差值为 0，不是摆动（既非正也非负），不能用于更新。 在代码中直接略过这部分即可

4. 循环结构与结果

总体 DP 流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
初始化：
    f[1][0] = f[1][1] = 1
    res = 1

循环 i = 2..n：
    f[i][0] = f[i][1] = 1   // 至少可以单独成为长度 1
    枚举 l = 1..i-1：
        if nums[i-1] > nums[l-1]:
            f[i][0] = max(f[i][0], f[l][1] + 1)
        else if nums[i-1] < nums[l-1]:
            f[i][1] = max(f[i][1], f[l][0] + 1)
    res = max(res, max(f[i][0], f[i][1]))

答案：
    return res

时间复杂度 O(n²)，在 n <= 1e3 的数据范围内是足够的。

二、贪心解法（O(n)）

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    const int maxn = 1e3 + 5;
    int wiggleMaxLength(vector<int>& nums) {
        int res = 1, p = 0;
        for (int i = 1; i < nums.size(); ++i) {
            int q;
            if (nums[i] - nums[i - 1] > 0)
                q = 1;
            else if (nums[i] - nums[i - 1] < 0)
                q = -1;
            else
                q = 0;
            if (!q)
                continue;
            if (p != q)
                ++res;
            p = q;
        }
        return res;
    }
};

我们重点要解释两件事：

  1. 为什么可以“删掉单调段中间的点”而不影响答案？
  2. 为什么这份代码正好在做“只数转折点，然后得到压缩后数组的长度”？

1. 用差值符号把问题抽象出来

对数组：

1
nums[0], nums[1], nums[2], ..., nums[n-1]

定义相邻差值：

1
diff[i] = nums[i] - nums[i-1],   i = 1..n-1

再抽象成符号：

1
2
3
sign(diff[i]) =  1  (diff[i] > 0)   上升
                 0  (diff[i] = 0)   水平
                -1  (diff[i] < 0)   下降

例如：

1
2
3
4
5
nums:        1    7    8    4    3    6    2
index:       0    1    2    3    4    5    6

diff:             6    1   -4   -1    3   -4
sign(diff):      +1   +1   -1   -1   +1   -1

用符号序列表示：

1
+  +  -  -  +  -

我们将分两步处理这个符号序列：

  1. 删掉所有 0（水平）
  2. 把连续相同的符号块压缩成一个

2. 删除单调段中间点：ASCII 图证明

2.1 连续上升段：中间点不可能是拐点

看一个连续上升的局部：

1
2
nums[i]   <   nums[j]   <   nums[k]
  3            5            8

画成粗糙的点阵图：

1
2
3
4
5
6
7
8
9
10
11
y
8           * (k)
7
6
5       * (j)
4
3   * (i)
2
1
0 -------------------------> index
    i       j       k

在这三个点中：

  • i -> j 是上升（+）
  • j -> k 也是上升（+）

如果在某个摆动子序列中，这三个点都出现且相邻：

1
..., nums[i], nums[j], nums[k], ...

这段的“符号序列”是：

1
+, +

也就是说： 这段内部不可能出现 “+ 变 -” 或 “- 变 +” 这种真正的拐点。

如果我们删掉中间点 j，变成：

1
..., nums[i], nums[k], ...

对应的符号是：

1
+         （只看 i->k）

从“摆动长度”的角度看，这两种情况：

  • ..., i, j, k, ...
  • ..., i, k, ...

都只贡献了一个“正差”到整体序列中，不会比后者更好。

因此： 在连续上升段中，所有中间点都可以不用选：

  • 最多只需保留这一段的两端（通常实际只保留右端那个更大的峰）

2.2 连续下降段：完全对称

连续下降：

1
2
nums[i]   >   nums[j]   >   nums[k]
  8            5            2

点阵图：

1
2
3
4
5
6
7
8
9
10
11
y
8   * (i)
7
6
5       * (j)
4
3
2           * (k)
1
0 -------------------------> index
    i       j       k

符号序列同样是：

1
-, -

同理，中间点 j 永远不可能成为一个“符号翻转点”，删掉不会让摆动长度变短。

因此：

在连续下降段中，所有中间点也可以删除，最多保留两端（通常实际保留右端那个更小的谷）。

2.3 把整个数组压缩后的形状

继续用之前的例子：

1
2
nums:  1    7    8    4    3    6    2
idx:   0    1    2    3    4    5    6

粗糙点阵画一下整体走势：

1
2
3
4
5
6
7
8
9
10
11
12
y
8           * (2)
7       * (1)
6                   * (5)
5
4               * (3)
3                 * (4)
2                         * (6)
1   * (0)
0 ----------------------------------> index
    0    1    2    3    4    5    6
    1    7    8    4    3    6    2

分段：

  • 1 → 7 → 8：连续上升段，删掉中间的 7，保留 [1, 8]
  • 8 → 4 → 3：连续下降段，删掉中间的 4，保留 [8, 3]
  • 3 → 6：上升
  • 6 → 2：下降

压缩后剩下的关键点：

1
[1, 8, 3, 6, 2]

再画一次压缩后的折线：

1
2
3
4
5
6
7
8
9
10
11
12
y
8           * (8)
7
6                   * (6)
5
4
3       * (3)
2                         * (2)
1   * (1)
0 ----------------------------------> 压缩后 index
    0    1    2    3    4
    1    8    3    6    2

对应的差值符号：

1
2
3
4
5
6
8 - 1 > 0   → +
3 - 8 < 0   → -
6 - 3 > 0   → +
2 - 6 < 0   → -

符号序列：+  -  +  -

可以看到：

  • 压缩后的数组已经是一个完美的摆动序列

  • 如果再删任何中间一个点，例如删掉 3：

    1
    2
    [1, 8, 6, 2]
    符号：+  -  -

    最后两个是 - -，不再严格交替，长度从 5 降为 4

因此：

删除所有单调段的中间点之后，剩下的这些离散的峰和谷，构成了一个最长摆动子序列； 其长度 = 原问题的答案。

3. 贪心代码实际上在做“在线压缩并计数”

再看贪心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int res = 1, p = 0;
for (int i = 1; i < nums.size(); ++i) {
    int q;
    if (nums[i] - nums[i - 1] > 0)
        q = 1;
    else if (nums[i] - nums[i - 1] < 0)
        q = -1;
    else
        q = 0;
    if (!q)
        continue;
    if (p != q)
        ++res;
    p = q;
}
return res;

变量含义：

  • q：当前一步的差值符号 sign(nums[i] - nums[i-1])
    • 1：当前是上升
    • -1：当前是下降
    • 0：当前是水平
  • p：上一段非 0 的差值符号（也就是当前“单调段”的方向）
  • res：当前统计出的压缩后数组长度（剩下峰谷个数）

解释循环逻辑：

  1. if (!q) continue; 差值为 0 的点，直接跳过，相当于不参与摆动。
  2. if (p != q) ++res;
    • 如果当前符号 q 和上一段方向 p 不同，则出现了“上升变下降”或“下降变上升”
    • 相当于在压缩后的数组中，新出现了一个峰或谷
    • 所以长度 res++
  3. p = q; 更新当前单调段的方向。

初始时：

  • res = 1：至少有一个点
  • p = 0：还没有方向

扫描过程等价于：

  1. 对 diff 求 sign，得到符号序列
  2. 删掉所有 0（水平段）
  3. 把连续相同的符号块压缩成一个：
    • 每出现一个新的符号块，就让 res++
  4. 最后 res 恰好等于压缩后数组的长度（峰谷个数）

也就是前面证明的这个结论：

“删除所有单调段中间点之后剩下的离散点的个数，就是答案”。

三、DP 与贪心的关系（简要）

  • DP 做的事： 明确地枚举所有可能的“以 i 结尾且最后一段为正/负”的最优子结构，复杂度 O(n²)。
  • 贪心做的事： 利用“单调段中间点永远不是转折点”的事实，边扫描边删掉所有单调中间点，只数符号翻转次数，复杂度 O(n)。

抽象地说：

  • DP 是“枚举所有可能的结尾状态然后取最大值”
  • 贪心是“用符号块压缩掉所有冗余状态，只保留峰与谷”

但在这道题里，两种做法得到的结果是严格相同的。