2501. 数组中最长的方波

发表于 分类于 阅读次数： Waline： 本文字数： 701 阅读时长 ≈ 2 分钟

考点

  • 线性DP

思路

1. 问题建模

给定一个整数数组 nums，定义一个平方链（square streak）为一个严格递增序列： \[ a_1, a_2, \dots, a_k \] 满足对任意 \(i \ge 1\)： \[ a_{i+1} = a_i^2 \] 并且所有元素都来自数组 nums。

目标

  • 求数组中最长平方链的长度
  • 若不存在长度 ≥ 2 的平方链，返回 -1

2. 建模思路

2.1 关键观察

  1. 数组中元素范围有限： \[ 2 \le nums[i] \le 10^5 \]

  2. 平方关系是单向且严格增大的： \[ x < x^2 \quad (x \ge 2) \]

  3. 每个数最多只有一个“后继”（平方值），因此图结构是一棵森林（多条链）

这使得问题非常适合用 动态规划（DP） 解决。

3. 状态定义

定义状态： \[ f(x) = \text{以 } x \text{ 为起点的最长平方链长度} \] 例如：

  • 若 x 在数组中，但 x^2 不存在，则： \[ f(x) = 1 \]

  • 若 x^2 也在数组中，则： \[ f(x) = 1 + f(x^2) \]

4. 状态转移方程（核心）

根据定义，可直接得到转移方程： \[ f(x) = \begin{cases} 1 + f(x^2), & \text{若 } x^2 \le 10^5 \\ 1, & \text{否则} \end{cases} \]

说明： 若 x^2 不在数组中，则 f(x^2) = 0，此时公式自然退化为 f(x) = 1，无需额外存在性判断。

5. 计算顺序与正确性说明

5.1 为什么要从大到小计算？

由于状态转移依赖于： \[ f(x) \leftarrow f(x^2) \] 而 \(x^2 > x\)，因此必须先计算较大的数，再计算较小的数。

实现策略

  1. 对 nums 排序
  2. 去重（避免重复计算）
  3. 按 降序遍历

这样可以保证在计算 f(x) 时，f(x^2) 已经就绪。

6. 答案提取

在 DP 过程中维护： \[ \text{mx} = \max_x f(x) \] 最终：

  • 若 mx < 2，说明不存在合法平方链，返回 -1
  • 否则返回 mx

7. 复杂度分析

  • 排序： \[ O(n \log n) \]

  • 动态规划遍历： \[ O(n) \]

  • 空间复杂度： \[ O(V), \quad V = 10^5 \]

该实现完全避免哈希结构，数组访问连续，常数极小，性能稳定。

8. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    // 最大值域上限
    static const int maxn = 1e5 + 5;
    static const int inf  = 1e5;

    int longestSquareStreak(vector<int>& nums) {
        // 排序，保证可以从大到小进行 DP
        sort(nums.begin(), nums.end());

        // 去重，避免重复状态计算
        int n = unique(nums.begin(), nums.end()) - nums.begin();

        // f[x] 表示以 x 为起点的最长平方链长度
        int f[maxn] = {};

        int mx = 0;
        long long x, y;

        // 从大到小遍历，确保 f[x^2] 已计算
        for (int i = n - 1; i >= 0; --i) {
            x = nums[i];
            y = x * x;

            // 基态：至少包含自身
            f[x] = 1;

            // 若平方值仍在合法值域内，则进行状态转移
            if (y <= inf) {
                f[x] = f[y] + 1;
                mx = max(mx, f[x]);
            }
        }

        // 长度小于 2 不构成平方链
        return mx < 2 ? -1 : mx;
    }
};