最长递增子序列的变种：每个元素最多使用k次的最长非递减子序列

字数 10831 2025-12-12 01:21:43

最长递增子序列的变种：每个元素最多使用k次的最长非递减子序列

题目描述
给定一个整数数组 nums 和一个正整数 k，我们需要找出一个最长的非递减子序列（子序列中的元素可以不连续，但保持原有顺序，且每个元素在原数组中最多可被使用 k 次），返回其长度。注意，这里的“最多使用 k 次”是指，在构造子序列时，可以从原数组的同一个索引位置最多选取该元素 k 次（但选取的必须是同一个值，相当于可以重复使用同一位置的值）。但题目更常见且合理的解释是：数组中的每个元素（值）可以被重复使用最多 k 次，但重复使用时，它们在子序列中必须作为不同的位置出现，且保持非递减顺序。实际上，这等价于：将原数组中的每个元素复制 k 份（即每个元素重复 k 次），然后在这扩展后的数组中，找一个最长非递减子序列（LNDS）。但为了效率，我们不会真的复制数组，而是用动态规划巧妙地处理。

例如，nums = [1,2,2,3]，k = 2，扩展后的数组（概念上）为 [1,2,2,2,2,3,3]（每个 1 出现 1 次，但可重复 k 次，但实际每个值重复 k 次）。最长非递减子序列可以是 [1,2,2,2,2,3,3] 全取，长度为 7。但注意在原数组中，每个位置的元素最多用 k 次，而值 2 在数组中出现 2 次（索引 1 和 2 处），每个索引处的 2 可以用 k=2 次，所以最多可使用 2*2=4 个 2。所以最长非递减子序列长度是 1（1 用 1 次）+ 4（2 用 4 次）+ 2（3 用 2 次）= 7。

我们的目标：设计一个 O(n log n) 或 O(nk) 的算法计算最长长度。

解题过程

步骤 1：问题转化
原问题可重新表述为：
给定数组 nums 长度 n，对每个元素值 nums[i]，我们可以使用它最多 k 次（在子序列中，每次使用都视为一个独立元素，且必须保持非递减顺序）。等价地，我们将每个元素 nums[i] 拆成 k 个相同的副本，但这些副本之间顺序固定（因为来自同一个位置，它们必须连续出现，且值相同）。但注意，不同位置可能有相同值，它们的副本可以交错。

更简单的理解：将原数组按值分组，对每个不同的值 v，设它在原数组中出现的次数为 count(v)，则我们最多可从这个值 v 中选取 min(count(v)k, ∞) 个元素到子序列中？不对，因为每个位置最多用 k 次，所以每个位置可以提供 k 个该值的元素。但子序列要求非递减，所以相同值可以连续出现任意次（只要不超过可用次数）。那么，如果我们把每个位置的每个可用副本都当成一个独立的“元素”，并按原数组顺序排列（对同一个位置，k 个副本连续），那么问题就转化为：在一个新序列中（长度为 nk），找出最长非递减子序列，但同一位置的 k 个副本必须按顺序取（因为值相同，非递减允许相等，所以可以全取）。但实际上，如果值相同，我们可以任意从不同位置交错取，只要每个位置使用的次数不超过 k 次。

关键观察：
设最终最长非递减子序列为 L。我们将 L 中的元素按值分类。对于值 v，假设我们需要用 t 个 v 在 L 中。这些 v 必须来自原数组中那些值等于 v 的位置，且每个位置 i（满足 nums[i]=v）最多提供 k 个。那么 t 的最大值 = min( m*k, t_max ) 其中 m 是值为 v 的位置个数。但 t 还要受前后值的限制（因为子序列要非递减，v 的前面必须是 ≤v 的值，后面必须是 ≥v 的值）。

所以我们需要一个动态规划，它考虑“使用每个值 v 最多允许的次数”来构造最长非递减子序列。

步骤 2：动态规划状态定义
一个经典的最长非递减子序列（LNDS）解法（O(n log n)）是维护一个数组 tails，其中 tails[l] 表示长度为 l 的递增子序列的最小末尾元素。但这里元素可重复使用 k 次，意味着同一个值可以在子序列中出现多次。
我们可以将原数组的每个元素复制 k 份，然后对这个扩展数组（长度为 nk）求 LNDS。但 nk 可能很大（k 可能大），需优化。

优化思路：
对每个位置 i，我们实际上可以生成 k 个相同的数 nums[i]。如果我们把这 k 个数按顺序排列（值相同），那么在做 LNDS 的贪心+二分算法时，相同的值会连续插入到 tails 数组的同一个位置或后面的位置吗？我们思考一下经典 LNDS 算法（允许非严格递增）：

维护数组 tails，tails[l] 是长度为 l 的递增子序列的末尾最小值。
对于每个新数 x，我们在 tails 中找到第一个大于 x 的位置，用 x 替换它（如果允许相等，则找第一个大于 x 的位置；如果允许非递减，则用 upper_bound 找第一个大于 x 的位置，用 x 替换）。
如果 x 大于等于所有 tails 的最后一个，就 append 到后面，长度+1。

现在，如果我们连续处理 k 个相同的 x，那么：

第一个 x：可能替换某个位置 pos 的元素（tails[pos] 是第一个大于 x 的位置），或者添加到末尾。
第二个 x：因为值相同，且 tails[pos] 现在等于 x，那么再遇到 x 时，upper_bound 会找到第一个大于 x 的位置，这个位置可能是 pos+1（如果 tails[pos+1] 大于 x）或者更后。这样，连续 k 个相同的 x 可能会使长度增加最多 k（如果原来 tails 里从 pos 开始后面有足够多的大于 x 的数可以被替换）。

但这样模拟相当于将每个 nums[i] 依次处理 k 次。复杂度 O(nk log L)，L 是最长长度，最坏 L 可达 nk，所以复杂度 O(nk log(nk))。若 k 很大则不可行。

步骤 3：更优的数学推导
我们考虑最终的 LNDS 中，每个值 v 会出现多少次。假设原数组中所有 ≤ v 的值能提供的最大长度我们已经知道。
定义 dp[v] 表示以值 v 结尾（实际用 v 填充最后一些位置）时，能获得的最大长度。但 v 是离散的，值域可能大，需要离散化。

设原数组的值已排序去重得到列表 vals。对于每个值 v，在原数组中出现的次数为 cnt[v]。我们最多可从 v 中取 cnt[v] * k 个副本，但在 LNDS 中，v 前面是 ≤ v 的值，所以如果我们决定在 LNDS 中放入 t 个 v，那么总长度 = 前面 ≤ v 的值能获得的最大长度 + t。

那么，对于值 v，我们想最大化总长度。前面 ≤ v 的值能获得的最大长度，就是所有小于 v 的值处理完后的最大长度，记作 prev_max。然后我们可以在后面添加 t 个 v，t 最大为 cnt[v] * k，但还要注意，添加的 v 不能太多以至于影响后面更大值的放置（因为 v 后面可以放更大的值，不影响）。实际上，我们可以先处理值小的，再处理值大的，因为非递减子序列一定是先小后大。

所以算法：

对原数组的值进行排序去重，得到值列表 vals 升序。
对每个值 v，计算它在原数组中出现的次数 cnt[v]。
初始化 max_len = 0。
按升序遍历每个值 v：
- 我们可以在当前已构造的序列末尾添加最多 cnt[v] * k 个 v，但添加后的总长度不能超过 max_len + cnt[v] * k，但实际是，添加 v 时，我们可以选择添加 t 个 v，t ≤ cnt[v] * k，并且添加后总长度变为 max_len + t，但 t 可以任意选择（不超过上限）。为了让后续更大的值能接着放，我们应尽可能多放 v 吗？注意，v 放再多也不影响后面更大的值，因为非递减允许相等，后面可以继续放大值。所以对于 v，我们应把 t 取最大值 cnt[v] * k，这样得到当前以 v 结尾的最长子序列长度 = max_len + cnt[v] * k。
- 更新 max_len = max(max_len, max_len + cnt[v] * k) 即 max_len += cnt[v] * k。

但这样对吗？看例子 nums=[1,2,2,3], k=2：
值 1 出现 1 次，cnt=1，max_len 初始 0 → max_len=0+12=2
值 2 出现 2 次，cnt=2，max_len=2+22=6
值 3 出现 1 次，cnt=1，max_len=6+12=8
但实际刚才我们算的最长是 7，不是 8。为什么呢？因为我们在每个值上乘以 k 是多算了。注意，原数组中每个位置最多用 k 次，但不同位置值相同时，它们的副本是分开的。但当我们按值统计时，我们将所有等于 v 的位置的副本一起用了，但同一个位置最多贡献 k 个副本，不同位置的副本在序列中可以交错，但总数不能超过 cnt[v]k。不过，在构造非递减子序列时，我们真的需要 cnt[v]*k 个 v 吗？在例子中，v=2 出现了 2 个位置，每个位置最多 2 次，所以最多 4 个副本，但实际用 4 个 2 时，序列会是 1,2,2,2,2,3,3，长度 7。但我们按公式算出 8，多了一个 2，是因为我们忘了：在放 2 之前，已经有前面的 1 用了 2 个副本（但 1 只有一个位置，最多用 2 个副本，但实际我们只需要 1 个 1 即可，因为再多放 1 会使序列更长吗？1 重复放不会减少长度，但 1 只有一个位置，最多用 k=2 次，所以可以放 2 个 1，即 1,1,2,... 但这样会更长吗？试试：1,1,2,2,2,2,3,3 → 长度 8。确实可以！为什么之前我认为是 7 呢？因为我误以为 1 只能用一次，但题目是每个元素（每个位置）最多用 k 次，不是每个值。原数组中只有一个 1，它在一个位置，可以重复 k=2 次，所以我们可以用两个 1。那么序列可以是：第一个位置用两次 1，接着第二个位置用两次 2，第三个位置用两次 2，第四个位置用两次 3，得到：1,1,2,2,2,2,3,3 长度 8。但这是非递减的，且每个位置用了 ≤2 次，符合条件。所以确实是 8。我之前例子算错了。

所以公式 max_len += cnt[v] * k 是对的，但前提是每个值 v 的所有位置都提供 k 个副本，且前面的值已经处理完，后面的值可以无缝追加。这样得到的是理论最大值：将所有元素每个用 k 次，总长度 n*k。但等等，如果 k 很大，序列会很长，但真的是非递减吗？是的，因为所有值按值大小顺序排列，每个值的所有副本连续出现，且值非递减。比如 nums=[2,1]，k=2，值排序后 [1,2]，cnt[1]=1, cnt[2]=1，max_len=2+2=4，序列 1,1,2,2 是非递减的，但原数组是 [2,1]，我们如何从原数组中取？我们需要原数组中 1 在 2 之后，但子序列要求顺序不变，原数组顺序是 2 在前 1 在后，我们无法得到 1,1,2,2，因为 1 在 2 后面，子序列必须保持原顺序，所以不能将 1 移到 2 前面。

所以我们的错误在于：我们没考虑原数组的顺序约束！我们只能按原数组顺序选取，不能先选小的再选大的，如果小的值出现在大的值后面，则不能排在前面。

步骤 4：考虑顺序约束的正确 DP
由于顺序约束，我们需要一个与经典 LIS 类似的 DP，但允许每个元素用最多 k 次。
一个巧妙的方法：将原数组每个元素复制 k 份，但保持复制后的顺序：对于原数组的每个位置 i，我们生成 k 个相同的数 nums[i]，它们连续排列。这样得到一个长度为 n*k 的数组 arr。然后在 arr 上求最长非递减子序列（LNDS），这就是答案。因为 arr 中每个位置代表原数组某个位置的一次使用，使用顺序必须和原数组顺序一致（因为同位置的 k 份连续，它们之间顺序任意，但值相同，非递减允许相等，所以这 k 份可以按任意数量选入子序列，但必须保持它们之间的相对顺序（因为是连续的，所以选后还是连续），但连续相同值在 LNDS 中我们可以全选，不影响）。所以问题等价于在 arr 上求 LNDS。

但 n*k 可能太大，需要优化。
观察：arr 是由 n 段组成的，每段是 k 个相同的数。在求 LNDS 时，对于一段相同值 x 的 k 个副本，由于值相同，在非递减序列中，它们可以全部被选入，且不会影响后面选更大的数（因为 x ≤ 后面更大的数）。但可能不会全选，因为前面结尾的数可能大于 x，那么这段 x 可能一个都不能选（如果前面结尾的数 > x，则不能非递减）。但经典 LNDS 算法（贪心+二分）可以处理这种情况：当遇到一个数 x 时，如果 x 小于当前某些长度为 l 的序列的末尾，我们会用 x 替换掉第一个大于 x 的数，从而可能允许后面更长的序列。当一段有 k 个相同的 x 时，第一个 x 可能会替换某个位置，第二个 x 可能替换下一个位置，直到这段 x 被用完或无法再增加长度。

步骤 5：高效模拟复制 k 份的效果
我们可以在贪心+二分的 LNDS 算法中，对每个位置 i 的数值 x，连续应用 k 次插入操作。但插入 k 次相同的 x，效果等价于：我们试图用 x 去替换 tails 数组中第一个大于 x 的位置，然后第二个 x 替换下一个大于 x 的位置，依此类推，最多替换 min(k, 大于 x 的位置数) 次。但注意，替换后 tails 中该位置的值变为 x，之后后面的 x 再去查找 upper_bound 时，可能会找到更后面的位置（因为 tails 数组是非递减的，所以相同值连续出现时，upper_bound 会找到下一个大于 x 的位置）。

所以过程：
对每个数 x，我们做以下操作 k 次：

在 tails 数组中找到第一个大于 x 的位置 pos（用 upper_bound，因为允许相等，所以找 >x 的第一个位置）。
如果 pos == tails.size()，说明 x 大于等于所有末尾，则 append x，长度+1。
否则，用 x 替换 tails[pos]。
然后继续处理同一个 x 的下一次。

但这样还是 O(nk log L) 时间，L ≤ nk。当 k 很大时仍大。

步骤 6：进一步优化
注意到 tails 数组是非递减的。当我们处理一段 k 个相同的 x 时，第一次用 x 替换 tails[pos] 后，tails[pos] 变成 x，那么第二次再处理 x 时，因为 tails[pos] 现在是 x，所以 upper_bound 会找到 pos+1（如果 tails[pos+1] > x）或更后。也就是说，这 k 个 x 会依次替换 tails 中从 pos 开始的连续若干个位置，只要这些位置的值 > x。
设 tails 中值 > x 的连续位置有 m 个（从第一个大于 x 的位置开始连续直到结尾或直到值不大于 x）。那么这 k 个 x 最多可以替换掉 min(k, m) 个位置，每次替换后，被替换的位置值变成 x，所以 m 可能会减少（因为被替换后该位置值变成 x，不再大于 x）。实际上，k 个 x 会使得 tails 中从起始位置 pos 开始的连续 min(k, m) 个位置都变成 x。
所以我们可以批量操作：

用 upper_bound 找到第一个大于 x 的位置 p。
在 tails 中从 p 开始，将后面最多 k 个位置的值设为 x，但前提是这些位置原来大于 x（如果遇到 ≤ x 则停止）。
但 tails 数组在批量替换后，可能会破坏非递减性吗？不会，因为替换成 x 后，这些位置的值都变成 x，而 x 小于等于后面的值（因为替换前 tails[p] > x，替换后 tails[p]=x，但 tails[p-1] ≤ x，所以仍然非递减）。

但实现时，我们不需要真的替换 k 次，我们只需要知道，这 k 个 x 可以让 tails 数组的“大于 x 的部分”被 x 覆盖一段，并可能扩展长度。
具体步骤：

在 tails 中用 upper_bound 找第一个大于 x 的位置 p。
设 remaining = k。
当 remaining > 0 且 p < tails.size() 且 tails[p] > x：
- 用 x 替换 tails[p]。
- p++。
- remaining--。
如果 remaining > 0，说明 tails 中从 p 开始的所有位置都 ≤ x 或者 p 到了末尾，那么我们可以将 x 添加到 tails 末尾 remaining 次（每次添加长度+1）。

但这样还是 O(nk) 时间（因为 remaining 可能 k 很大，我们要添加很多次）。但注意到，当 remaining 很大时，我们会连续在 tails 末尾添加 x，这会导致 tails 末尾有一大段相同的 x。我们能否批量添加？可以：我们直接添加 remaining 个 x 到 tails 末尾，长度增加 remaining。但这样正确吗？在贪心算法中，每次添加一个 x 到末尾，是合法的，因为 x 大于等于之前末尾的值。连续添加多个相同的 x 到末尾，tails 仍然保持非递减，且长度增加了 remaining。所以可以批量添加。

那么批量替换部分呢？替换时，我们一次替换一个位置，但 remaining 可能很大，我们需要循环。但 tails 中大于 x 的位置可能不多，所以循环次数不会超过 tails 长度，而 tails 长度 ≤ n*k，最坏仍是 O(nk)。但我们可以优化：因为 tails 是非递减的，大于 x 的位置是连续的一段，设从位置 p 开始到位置 q-1 都是 > x 的，q 是第一个 ≤ x 的位置或末尾。那么我们可以用 x 替换其中前 min(k, q-p) 个位置，即把 tails[p: p+min(k, q-p)] 赋值成 x。这可以用二分找到 q（第一个 ≤ x 的位置），然后批量赋值。但赋值后，tails 中这段变成 x，可能破坏非递减性吗？不会，因为 tails[p-1] ≤ x ≤ tails[q]（如果 q 存在），所以非递减保持。然后如果 k > (q-p)，则剩下的 k' = k - (q-p) 个 x 可以添加到末尾（因为 tails 中 p 到 q-1 都变成了 x，后面都大于等于 x，所以再加 x 到末尾也可以）。

但实现时，我们不必真的存储整个 tails 数组，因为 tails 会很长（可能 n*k 大）。但我们知道 tails 是递增的，我们可以存储每个值的个数。不过这样复杂。

实际上，经典 LIS 的贪心+二分算法中，tails 数组的长度就是当前找到的 LIS 长度，而 tails 本身是递增的。当 k 很大时，长度可能达到 nk，但 nk 可能很大（比如 10^5 * 10^5），无法存储。但题目通常 k 不会太大（比如 k ≤ 10^5）。我们假设 n 和 k 都在 10^5 以内，那么 n*k 可能 10^10，太大。所以我们需要更优方法。

步骤 7：O(n log n) 解法
实际上，这个问题有一个 O(n log n) 的解法，利用每个值最多用 k 次这个条件，我们可以对每个值 v，计算它能在 LNDS 中出现的最多次数。
定义 dp[x] 表示以值 x 结尾的子序列的最大长度。但 x 是值域大，需要离散化。
转移：dp[x] = max(dp[y] for y ≤ x) + add[x]，其中 add[x] 是值 x 最多能贡献的长度，即 cnt[x] * k。但这是错误的，因为 dp[x] 表示以 x 结尾，前面可以接 ≤ x 的值，但前面 ≤ x 的值可能已经占用了某些位置，而 x 的副本可以接在后面，数量最多 cnt[x]*k，但可能受限于前面的值的结束位置？不对，因为非递减，x 可以接在任何 ≤ x 的值后面，且可以连续放多个 x。

更准确的：设 f[x] 为考虑所有值 ≤ x 时，能得到的最大长度。那么 f[x] = f[prev(x)] + min(cnt[x]k, ∞)，其中 prev(x) 是比 x 小的前一个值。因为当我们已经构造了一个最长非递减序列用了所有 ≤ prev(x) 的值，现在考虑值 x，我们可以在这个序列后面添加 cnt[x]k 个 x，序列仍然非递减。但这里假设了 x 的所有副本都可以在 prev(x) 的后面添加，这要求原数组中 x 的位置都在 prev(x) 的位置之后吗？不，因为子序列不要求连续，我们可以从原数组中按顺序选取，只要值非递减。如果某个 x 出现在某个 prev(x) 之前，我们也可以先取 prev(x) 后取 x，只要原数组中存在一个顺序使得 prev(x) 在 x 之前出现。但原数组中值小的可能在值大的后面，这没关系，我们可以在构造子序列时跳过那些不满足顺序的。但我们的 f[x] 是按值大小顺序递推的，没有考虑原数组顺序，会出错，如之前的例子 [2,1]，k=2，按值 1 再 2，f[1]=2，f[2]=f[1]+2=4，但实际不可能，因为 1 在 2 后面，无法构成 1,1,2,2。

所以顺序很重要。我们需要一个基于位置的 DP。

步骤 8：最终正确的高效算法
实际上，这个问题可以转化为：将原数组每个元素扩展成 k 个相同值，然后在这些值序列上求 LNDS。但我们可以用平衡树或线段树优化，达到 O(n log n)。

思路：
我们维护一个有序映射（如 C++ 的 map），记录当前每个可能的结尾值对应的最大长度。
遍历原数组每个位置 i 的值 x：

我们需要考虑使用这个位置的 1 到 k 次。但使用多次相当于插入多个 x。
我们可以这样：对于每个 x，我们尝试将其插入当前的 LNDS 中，最多 k 次。但插入 k 次相当于，我们找到当前 tails 中第一个大于 x 的位置，然后用 x 替换它，然后继续找下一个大于 x 的位置，替换，重复最多 k 次。这可以用平衡树实现：tails 用平衡树维护，每个值可能出现多次（因为值可重复）。当我们处理 x 时，我们在平衡树中找到第一个大于 x 的迭代器 it，如果 it 不存在，则添加 k 个 x 到树中（长度增加 k）。如果 it 存在，则用 x 替换它，并删除它，然后继续找下一个大于 x 的迭代器，重复直到用完 k 次或没有大于 x 的元素。但每次替换，我们只是将树中的一个大于 x 的值替换为 x，相当于删去一个大于 x 的值，插入一个 x。但这样可能会使树中 x 的个数增加。
实际上，我们可以一次性完成：在树中，所有大于 x 的值，我们最多可以替换前 k 个（按值升序），将它们变成 x。然后，如果还有剩余的 x 要插入，则直接插入 x（即添加到末尾）。

但我们不能真的替换 k 次，因为 k 可能大。我们可以用计数来优化：树中存储每个值的出现次数。对于当前 x，我们找到第一个大于 x 的值 y，设其出现次数为 c，我们可以将 min(c, k) 个 y 替换成 x（即减少 c 个 y，增加 min(c,k) 个 x），然后 k 减去 min(c,k)，继续找下一个大于 x 的值，直到 k=0 或没有大于 x 的值。如果最后 k>0，则添加 k 个 x 到树中。

这样，每个 x 处理时，可能会删除多个不同的 y，但每个 y 只会被处理一次（因为一旦变成 x，就不再大于 x）。总复杂度 O(n log M)，M 是树中不同值的个数。

但实现复杂。

步骤 9：一个简单且正确的算法
由于 n 和 k 可能不大（在竞赛中常限制 n*k ≤ 10^7），我们可以直接用扩展数组 + 贪心二分。
即：

构建数组 arr：对原数组 nums 的每个元素，重复 k 次，加入 arr。
在 arr 上运行经典的非递减子序列的贪心二分算法（用 upper_bound 找第一个大于当前数 x 的位置，替换；如果找不到，则追加）。
最终 tails 的长度即为答案。

时间复杂度 O(nk log(nk))，空间 O(nk)。当 n*k 不太大时可行。

步骤 10：举例
nums = [1,2,2,3], k=2
arr = [1,1,2,2,2,2,3,3]
运行 LNDS 贪心算法：

1: tails=[1]
1: upper_bound(1) 找 >1 → 没找到，append → tails=[1,1]
2: upper_bound(2) → 没找到，append → tails=[1,1,2]
2: upper_bound(2) → 没找到，append → tails=[1,1,2,2]
2: upper_bound(2) → 没找到，append → tails=[1,1,2,2,2]
2: upper_bound(2) → 没找到，append → tails=[1,1,2,2,2,2]
3: upper_bound(3) → 没找到，append → tails=[1,1,2,2,2,2,3]
3: upper_bound(3) → 没找到，append → tails=[1,1,2,2,2,2,3,3]
长度 8。

步骤 11：总结
这个问题本质上是经典 LIS 的变种，允许每个元素重复使用最多 k 次。最直观的方法是将原数组每个元素复制 k 次，形成新数组，然后在新数组上求最长非递减子序列。
如果 nk 在可接受范围，可以直接用贪心+二分求解，时间复杂度 O(nk log(nk))。
如果 nk 太大，需要用平衡树优化替换过程，达到 O(n log M) 复杂度，其中 M 是值域大小。
在实际编程中，根据数据范围选择合适方法即可。

最长递增子序列的变种：每个元素最多使用k次的最长非递减子序列题目描述给定一个整数数组 nums 和一个正整数 k ，我们需要找出一个最长的非递减子序列（子序列中的元素可以不连续，但保持原有顺序，且每个元素在原数组中最多可被使用 k 次），返回其长度。注意，这里的“最多使用 k 次”是指，在构造子序列时，可以从原数组的同一个索引位置最多选取该元素 k 次（但选取的必须是同一个值，相当于可以重复使用同一位置的值）。但题目更常见且合理的解释是：数组中的每个元素（值）可以被重复使用最多 k 次，但重复使用时，它们在子序列中必须作为不同的位置出现，且保持非递减顺序。实际上，这等价于：将原数组中的每个元素复制 k 份（即每个元素重复 k 次），然后在这扩展后的数组中，找一个最长非递减子序列（LNDS）。但为了效率，我们不会真的复制数组，而是用动态规划巧妙地处理。例如， nums = [1,2,2,3] ， k = 2 ，扩展后的数组（概念上）为 [1,2,2,2,2,3,3] （每个 1 出现 1 次，但可重复 k 次，但实际每个值重复 k 次）。最长非递减子序列可以是 [1,2,2,2,2,3,3] 全取，长度为 7。但注意在原数组中，每个位置的元素最多用 k 次，而值 2 在数组中出现 2 次（索引 1 和 2 处），每个索引处的 2 可以用 k=2 次，所以最多可使用 2* 2=4 个 2。所以最长非递减子序列长度是 1（1 用 1 次）+ 4（2 用 4 次）+ 2（3 用 2 次）= 7。我们的目标：设计一个 O(n log n) 或 O(nk) 的算法计算最长长度。解题过程步骤 1：问题转化原问题可重新表述为：给定数组 nums 长度 n，对每个元素值 nums[i] ，我们可以使用它最多 k 次（在子序列中，每次使用都视为一个独立元素，且必须保持非递减顺序）。等价地，我们将每个元素 nums[i] 拆成 k 个相同的副本，但这些副本之间顺序固定（因为来自同一个位置，它们必须连续出现，且值相同）。但注意，不同位置可能有相同值，它们的副本可以交错。更简单的理解：将原数组按值分组，对每个不同的值 v，设它在原数组中出现的次数为 count(v)，则我们最多可从这个值 v 中选取 min(count(v) k, ∞) 个元素到子序列中？不对，因为每个位置最多用 k 次，所以每个位置可以提供 k 个该值的元素。但子序列要求非递减，所以相同值可以连续出现任意次（只要不超过可用次数）。那么，如果我们把每个位置的每个可用副本都当成一个独立的“元素”，并按原数组顺序排列（对同一个位置，k 个副本连续），那么问题就转化为：在一个新序列中（长度为 n k），找出最长非递减子序列，但同一位置的 k 个副本必须按顺序取（因为值相同，非递减允许相等，所以可以全取）。但实际上，如果值相同，我们可以任意从不同位置交错取，只要每个位置使用的次数不超过 k 次。关键观察：设最终最长非递减子序列为 L。我们将 L 中的元素按值分类。对于值 v，假设我们需要用 t 个 v 在 L 中。这些 v 必须来自原数组中那些值等于 v 的位置，且每个位置 i（满足 nums[ i]=v）最多提供 k 个。那么 t 的最大值 = min( m* k, t_ max ) 其中 m 是值为 v 的位置个数。但 t 还要受前后值的限制（因为子序列要非递减，v 的前面必须是 ≤v 的值，后面必须是 ≥v 的值）。所以我们需要一个动态规划，它考虑“使用每个值 v 最多允许的次数”来构造最长非递减子序列。步骤 2：动态规划状态定义一个经典的最长非递减子序列（LNDS）解法（O(n log n)）是维护一个数组 tails ，其中 tails[l] 表示长度为 l 的递增子序列的最小末尾元素。但这里元素可重复使用 k 次，意味着同一个值可以在子序列中出现多次。我们可以将原数组的每个元素复制 k 份，然后对这个扩展数组（长度为 n k）求 LNDS。但 n k 可能很大（k 可能大），需优化。优化思路：对每个位置 i，我们实际上可以生成 k 个相同的数 nums[ i]。如果我们把这 k 个数按顺序排列（值相同），那么在做 LNDS 的贪心+二分算法时，相同的值会连续插入到 tails 数组的同一个位置或后面的位置吗？我们思考一下经典 LNDS 算法（允许非严格递增）：维护数组 tails ， tails[l] 是长度为 l 的递增子序列的末尾最小值。对于每个新数 x，我们在 tails 中找到第一个大于 x 的位置，用 x 替换它（如果允许相等，则找第一个大于 x 的位置；如果允许非递减，则用 upper_bound 找第一个大于 x 的位置，用 x 替换）。如果 x 大于等于所有 tails 的最后一个，就 append 到后面，长度+1。现在，如果我们连续处理 k 个相同的 x，那么：第一个 x：可能替换某个位置 pos 的元素（ tails[pos] 是第一个大于 x 的位置），或者添加到末尾。第二个 x：因为值相同，且 tails[pos] 现在等于 x，那么再遇到 x 时， upper_bound 会找到第一个大于 x 的位置，这个位置可能是 pos+1（如果 tails[pos+1] 大于 x）或者更后。这样，连续 k 个相同的 x 可能会使长度增加最多 k（如果原来 tails 里从 pos 开始后面有足够多的大于 x 的数可以被替换）。但这样模拟相当于将每个 nums[ i ] 依次处理 k 次。复杂度 O(nk log L)，L 是最长长度，最坏 L 可达 nk，所以复杂度 O(nk log(nk))。若 k 很大则不可行。步骤 3：更优的数学推导我们考虑最终的 LNDS 中，每个值 v 会出现多少次。假设原数组中所有 ≤ v 的值能提供的最大长度我们已经知道。定义 dp[v] 表示以值 v 结尾（实际用 v 填充最后一些位置）时，能获得的最大长度。但 v 是离散的，值域可能大，需要离散化。设原数组的值已排序去重得到列表 vals 。对于每个值 v，在原数组中出现的次数为 cnt[v] 。我们最多可从 v 中取 cnt[v] * k 个副本，但在 LNDS 中，v 前面是 ≤ v 的值，所以如果我们决定在 LNDS 中放入 t 个 v，那么总长度 = 前面 ≤ v 的值能获得的最大长度 + t。那么，对于值 v，我们想最大化总长度。前面 ≤ v 的值能获得的最大长度，就是所有小于 v 的值处理完后的最大长度，记作 prev_max 。然后我们可以在后面添加 t 个 v，t 最大为 cnt[v] * k ，但还要注意，添加的 v 不能太多以至于影响后面更大值的放置（因为 v 后面可以放更大的值，不影响）。实际上，我们可以先处理值小的，再处理值大的，因为非递减子序列一定是先小后大。所以算法：对原数组的值进行排序去重，得到值列表 vals 升序。对每个值 v，计算它在原数组中出现的次数 cnt[ v ]。初始化 max_len = 0 。按升序遍历每个值 v：我们可以在当前已构造的序列末尾添加最多 cnt[ v] * k 个 v，但添加后的总长度不能超过 max_ len + cnt[ v] * k，但实际是，添加 v 时，我们可以选择添加 t 个 v，t ≤ cnt[ v] * k，并且添加后总长度变为 max_ len + t，但 t 可以任意选择（不超过上限）。为了让后续更大的值能接着放，我们应尽可能多放 v 吗？注意，v 放再多也不影响后面更大的值，因为非递减允许相等，后面可以继续放大值。所以对于 v，我们应把 t 取最大值 cnt[ v] * k，这样得到当前以 v 结尾的最长子序列长度 = max_ len + cnt[ v] * k。更新 max_ len = max(max_ len, max_ len + cnt[ v] * k) 即 max_ len += cnt[ v] * k。但这样对吗？看例子 nums=[ 1,2,2,3 ], k=2：值 1 出现 1 次，cnt=1，max_ len 初始 0 → max_ len=0+1 2=2 值 2 出现 2 次，cnt=2，max_ len=2+2 2=6 值 3 出现 1 次，cnt=1，max_ len=6+1 2=8 但实际刚才我们算的最长是 7，不是 8。为什么呢？因为我们在每个值上乘以 k 是多算了。注意，原数组中每个位置最多用 k 次，但不同位置值相同时，它们的副本是分开的。但当我们按值统计时，我们将所有等于 v 的位置的副本一起用了，但同一个位置最多贡献 k 个副本，不同位置的副本在序列中可以交错，但总数不能超过 cnt[ v] k。不过，在构造非递减子序列时，我们真的需要 cnt[ v]* k 个 v 吗？在例子中，v=2 出现了 2 个位置，每个位置最多 2 次，所以最多 4 个副本，但实际用 4 个 2 时，序列会是 1,2,2,2,2,3,3，长度 7。但我们按公式算出 8，多了一个 2，是因为我们忘了：在放 2 之前，已经有前面的 1 用了 2 个副本（但 1 只有一个位置，最多用 2 个副本，但实际我们只需要 1 个 1 即可，因为再多放 1 会使序列更长吗？1 重复放不会减少长度，但 1 只有一个位置，最多用 k=2 次，所以可以放 2 个 1，即 1,1,2,... 但这样会更长吗？试试：1,1,2,2,2,2,3,3 → 长度 8。确实可以！为什么之前我认为是 7 呢？因为我误以为 1 只能用一次，但题目是每个元素（每个位置）最多用 k 次，不是每个值。原数组中只有一个 1，它在一个位置，可以重复 k=2 次，所以我们可以用两个 1。那么序列可以是：第一个位置用两次 1，接着第二个位置用两次 2，第三个位置用两次 2，第四个位置用两次 3，得到：1,1,2,2,2,2,3,3 长度 8。但这是非递减的，且每个位置用了 ≤2 次，符合条件。所以确实是 8。我之前例子算错了。所以公式 max_ len += cnt[ v] * k 是对的，但前提是每个值 v 的所有位置都提供 k 个副本，且前面的值已经处理完，后面的值可以无缝追加。这样得到的是理论最大值：将所有元素每个用 k 次，总长度 n* k。但等等，如果 k 很大，序列会很长，但真的是非递减吗？是的，因为所有值按值大小顺序排列，每个值的所有副本连续出现，且值非递减。比如 nums=[ 2,1]，k=2，值排序后 [ 1,2]，cnt[ 1]=1, cnt[ 2]=1，max_ len=2+2=4，序列 1,1,2,2 是非递减的，但原数组是 [ 2,1 ]，我们如何从原数组中取？我们需要原数组中 1 在 2 之后，但子序列要求顺序不变，原数组顺序是 2 在前 1 在后，我们无法得到 1,1,2,2，因为 1 在 2 后面，子序列必须保持原顺序，所以不能将 1 移到 2 前面。所以我们的错误在于：我们没考虑原数组的顺序约束！我们只能按原数组顺序选取，不能先选小的再选大的，如果小的值出现在大的值后面，则不能排在前面。步骤 4：考虑顺序约束的正确 DP 由于顺序约束，我们需要一个与经典 LIS 类似的 DP，但允许每个元素用最多 k 次。一个巧妙的方法：将原数组每个元素复制 k 份，但保持复制后的顺序：对于原数组的每个位置 i，我们生成 k 个相同的数 nums[ i]，它们连续排列。这样得到一个长度为 n* k 的数组 arr。然后在 arr 上求最长非递减子序列（LNDS），这就是答案。因为 arr 中每个位置代表原数组某个位置的一次使用，使用顺序必须和原数组顺序一致（因为同位置的 k 份连续，它们之间顺序任意，但值相同，非递减允许相等，所以这 k 份可以按任意数量选入子序列，但必须保持它们之间的相对顺序（因为是连续的，所以选后还是连续），但连续相同值在 LNDS 中我们可以全选，不影响）。所以问题等价于在 arr 上求 LNDS。但 n* k 可能太大，需要优化。观察：arr 是由 n 段组成的，每段是 k 个相同的数。在求 LNDS 时，对于一段相同值 x 的 k 个副本，由于值相同，在非递减序列中，它们可以全部被选入，且不会影响后面选更大的数（因为 x ≤ 后面更大的数）。但可能不会全选，因为前面结尾的数可能大于 x，那么这段 x 可能一个都不能选（如果前面结尾的数 > x，则不能非递减）。但经典 LNDS 算法（贪心+二分）可以处理这种情况：当遇到一个数 x 时，如果 x 小于当前某些长度为 l 的序列的末尾，我们会用 x 替换掉第一个大于 x 的数，从而可能允许后面更长的序列。当一段有 k 个相同的 x 时，第一个 x 可能会替换某个位置，第二个 x 可能替换下一个位置，直到这段 x 被用完或无法再增加长度。步骤 5：高效模拟复制 k 份的效果我们可以在贪心+二分的 LNDS 算法中，对每个位置 i 的数值 x，连续应用 k 次插入操作。但插入 k 次相同的 x，效果等价于：我们试图用 x 去替换 tails 数组中第一个大于 x 的位置，然后第二个 x 替换下一个大于 x 的位置，依此类推，最多替换 min(k, 大于 x 的位置数) 次。但注意，替换后 tails 中该位置的值变为 x，之后后面的 x 再去查找 upper_ bound 时，可能会找到更后面的位置（因为 tails 数组是非递减的，所以相同值连续出现时，upper_ bound 会找到下一个大于 x 的位置）。所以过程：对每个数 x，我们做以下操作 k 次：在 tails 数组中找到第一个大于 x 的位置 pos（用 upper_ bound，因为允许相等，所以找 >x 的第一个位置）。如果 pos == tails.size()，说明 x 大于等于所有末尾，则 append x，长度+1。否则，用 x 替换 tails[ pos ]。然后继续处理同一个 x 的下一次。但这样还是 O(nk log L) 时间，L ≤ nk。当 k 很大时仍大。步骤 6：进一步优化注意到 tails 数组是非递减的。当我们处理一段 k 个相同的 x 时，第一次用 x 替换 tails[ pos] 后，tails[ pos] 变成 x，那么第二次再处理 x 时，因为 tails[ pos] 现在是 x，所以 upper_ bound 会找到 pos+1（如果 tails[ pos+1 ] > x）或更后。也就是说，这 k 个 x 会依次替换 tails 中从 pos 开始的连续若干个位置，只要这些位置的值 > x。设 tails 中值 > x 的连续位置有 m 个（从第一个大于 x 的位置开始连续直到结尾或直到值不大于 x）。那么这 k 个 x 最多可以替换掉 min(k, m) 个位置，每次替换后，被替换的位置值变成 x，所以 m 可能会减少（因为被替换后该位置值变成 x，不再大于 x）。实际上，k 个 x 会使得 tails 中从起始位置 pos 开始的连续 min(k, m) 个位置都变成 x。所以我们可以批量操作：用 upper_ bound 找到第一个大于 x 的位置 p。在 tails 中从 p 开始，将后面最多 k 个位置的值设为 x，但前提是这些位置原来大于 x（如果遇到 ≤ x 则停止）。但 tails 数组在批量替换后，可能会破坏非递减性吗？不会，因为替换成 x 后，这些位置的值都变成 x，而 x 小于等于后面的值（因为替换前 tails[ p] > x，替换后 tails[ p]=x，但 tails[ p-1 ] ≤ x，所以仍然非递减）。但实现时，我们不需要真的替换 k 次，我们只需要知道，这 k 个 x 可以让 tails 数组的“大于 x 的部分”被 x 覆盖一段，并可能扩展长度。具体步骤：在 tails 中用 upper_ bound 找第一个大于 x 的位置 p。设 remaining = k。当 remaining > 0 且 p < tails.size() 且 tails[ p ] > x：用 x 替换 tails[ p ]。 p++。 remaining--。如果 remaining > 0，说明 tails 中从 p 开始的所有位置都 ≤ x 或者 p 到了末尾，那么我们可以将 x 添加到 tails 末尾 remaining 次（每次添加长度+1）。但这样还是 O(nk) 时间（因为 remaining 可能 k 很大，我们要添加很多次）。但注意到，当 remaining 很大时，我们会连续在 tails 末尾添加 x，这会导致 tails 末尾有一大段相同的 x。我们能否批量添加？可以：我们直接添加 remaining 个 x 到 tails 末尾，长度增加 remaining。但这样正确吗？在贪心算法中，每次添加一个 x 到末尾，是合法的，因为 x 大于等于之前末尾的值。连续添加多个相同的 x 到末尾，tails 仍然保持非递减，且长度增加了 remaining。所以可以批量添加。那么批量替换部分呢？替换时，我们一次替换一个位置，但 remaining 可能很大，我们需要循环。但 tails 中大于 x 的位置可能不多，所以循环次数不会超过 tails 长度，而 tails 长度 ≤ n* k，最坏仍是 O(nk)。但我们可以优化：因为 tails 是非递减的，大于 x 的位置是连续的一段，设从位置 p 开始到位置 q-1 都是 > x 的，q 是第一个 ≤ x 的位置或末尾。那么我们可以用 x 替换其中前 min(k, q-p) 个位置，即把 tails[ p: p+min(k, q-p)] 赋值成 x。这可以用二分找到 q（第一个 ≤ x 的位置），然后批量赋值。但赋值后，tails 中这段变成 x，可能破坏非递减性吗？不会，因为 tails[ p-1] ≤ x ≤ tails[ q ]（如果 q 存在），所以非递减保持。然后如果 k > (q-p)，则剩下的 k' = k - (q-p) 个 x 可以添加到末尾（因为 tails 中 p 到 q-1 都变成了 x，后面都大于等于 x，所以再加 x 到末尾也可以）。但实现时，我们不必真的存储整个 tails 数组，因为 tails 会很长（可能 n* k 大）。但我们知道 tails 是递增的，我们可以存储每个值的个数。不过这样复杂。实际上，经典 LIS 的贪心+二分算法中，tails 数组的长度就是当前找到的 LIS 长度，而 tails 本身是递增的。当 k 很大时，长度可能达到 n k，但 n k 可能很大（比如 10^5 * 10^5），无法存储。但题目通常 k 不会太大（比如 k ≤ 10^5）。我们假设 n 和 k 都在 10^5 以内，那么 n* k 可能 10^10，太大。所以我们需要更优方法。步骤 7：O(n log n) 解法实际上，这个问题有一个 O(n log n) 的解法，利用每个值最多用 k 次这个条件，我们可以对每个值 v，计算它能在 LNDS 中出现的最多次数。定义 dp[ x ] 表示以值 x 结尾的子序列的最大长度。但 x 是值域大，需要离散化。转移：dp[ x] = max(dp[ y] for y ≤ x) + add[ x]，其中 add[ x] 是值 x 最多能贡献的长度，即 cnt[ x] * k。但这是错误的，因为 dp[ x] 表示以 x 结尾，前面可以接 ≤ x 的值，但前面 ≤ x 的值可能已经占用了某些位置，而 x 的副本可以接在后面，数量最多 cnt[ x]* k，但可能受限于前面的值的结束位置？不对，因为非递减，x 可以接在任何 ≤ x 的值后面，且可以连续放多个 x。更准确的：设 f[ x] 为考虑所有值 ≤ x 时，能得到的最大长度。那么 f[ x] = f[ prev(x)] + min(cnt[ x] k, ∞)，其中 prev(x) 是比 x 小的前一个值。因为当我们已经构造了一个最长非递减序列用了所有 ≤ prev(x) 的值，现在考虑值 x，我们可以在这个序列后面添加 cnt[ x] k 个 x，序列仍然非递减。但这里假设了 x 的所有副本都可以在 prev(x) 的后面添加，这要求原数组中 x 的位置都在 prev(x) 的位置之后吗？不，因为子序列不要求连续，我们可以从原数组中按顺序选取，只要值非递减。如果某个 x 出现在某个 prev(x) 之前，我们也可以先取 prev(x) 后取 x，只要原数组中存在一个顺序使得 prev(x) 在 x 之前出现。但原数组中值小的可能在值大的后面，这没关系，我们可以在构造子序列时跳过那些不满足顺序的。但我们的 f[ x] 是按值大小顺序递推的，没有考虑原数组顺序，会出错，如之前的例子 [ 2,1]，k=2，按值 1 再 2，f[ 1]=2，f[ 2]=f[ 1 ]+2=4，但实际不可能，因为 1 在 2 后面，无法构成 1,1,2,2。所以顺序很重要。我们需要一个基于位置的 DP。步骤 8：最终正确的高效算法实际上，这个问题可以转化为：将原数组每个元素扩展成 k 个相同值，然后在这些值序列上求 LNDS。但我们可以用平衡树或线段树优化，达到 O(n log n)。思路：我们维护一个有序映射（如 C++ 的 map），记录当前每个可能的结尾值对应的最大长度。遍历原数组每个位置 i 的值 x：我们需要考虑使用这个位置的 1 到 k 次。但使用多次相当于插入多个 x。我们可以这样：对于每个 x，我们尝试将其插入当前的 LNDS 中，最多 k 次。但插入 k 次相当于，我们找到当前 tails 中第一个大于 x 的位置，然后用 x 替换它，然后继续找下一个大于 x 的位置，替换，重复最多 k 次。这可以用平衡树实现：tails 用平衡树维护，每个值可能出现多次（因为值可重复）。当我们处理 x 时，我们在平衡树中找到第一个大于 x 的迭代器 it，如果 it 不存在，则添加 k 个 x 到树中（长度增加 k）。如果 it 存在，则用 x 替换它，并删除它，然后继续找下一个大于 x 的迭代器，重复直到用完 k 次或没有大于 x 的元素。但每次替换，我们只是将树中的一个大于 x 的值替换为 x，相当于删去一个大于 x 的值，插入一个 x。但这样可能会使树中 x 的个数增加。实际上，我们可以一次性完成：在树中，所有大于 x 的值，我们最多可以替换前 k 个（按值升序），将它们变成 x。然后，如果还有剩余的 x 要插入，则直接插入 x（即添加到末尾）。但我们不能真的替换 k 次，因为 k 可能大。我们可以用计数来优化：树中存储每个值的出现次数。对于当前 x，我们找到第一个大于 x 的值 y，设其出现次数为 c，我们可以将 min(c, k) 个 y 替换成 x（即减少 c 个 y，增加 min(c,k) 个 x），然后 k 减去 min(c,k)，继续找下一个大于 x 的值，直到 k=0 或没有大于 x 的值。如果最后 k>0，则添加 k 个 x 到树中。这样，每个 x 处理时，可能会删除多个不同的 y，但每个 y 只会被处理一次（因为一旦变成 x，就不再大于 x）。总复杂度 O(n log M)，M 是树中不同值的个数。但实现复杂。步骤 9：一个简单且正确的算法由于 n 和 k 可能不大（在竞赛中常限制 n* k ≤ 10^7），我们可以直接用扩展数组 + 贪心二分。即：构建数组 arr：对原数组 nums 的每个元素，重复 k 次，加入 arr。在 arr 上运行经典的非递减子序列的贪心二分算法（用 upper_ bound 找第一个大于当前数 x 的位置，替换；如果找不到，则追加）。最终 tails 的长度即为答案。时间复杂度 O(nk log(nk))，空间 O(nk)。当 n* k 不太大时可行。步骤 10：举例 nums = [ 1,2,2,3 ], k=2 arr = [ 1,1,2,2,2,2,3,3 ] 运行 LNDS 贪心算法： 1: tails=[ 1 ] 1: upper_ bound(1) 找 >1 → 没找到，append → tails=[ 1,1 ] 2: upper_ bound(2) → 没找到，append → tails=[ 1,1,2 ] 2: upper_ bound(2) → 没找到，append → tails=[ 1,1,2,2 ] 2: upper_ bound(2) → 没找到，append → tails=[ 1,1,2,2,2 ] 2: upper_ bound(2) → 没找到，append → tails=[ 1,1,2,2,2,2 ] 3: upper_ bound(3) → 没找到，append → tails=[ 1,1,2,2,2,2,3 ] 3: upper_ bound(3) → 没找到，append → tails=[ 1,1,2,2,2,2,3,3 ] 长度 8。步骤 11：总结这个问题本质上是经典 LIS 的变种，允许每个元素重复使用最多 k 次。最直观的方法是将原数组每个元素复制 k 次，形成新数组，然后在新数组上求最长非递减子序列。如果 n k 在可接受范围，可以直接用贪心+二分求解，时间复杂度 O(nk log(nk))。如果 n k 太大，需要用平衡树优化替换过程，达到 O(n log M) 复杂度，其中 M 是值域大小。在实际编程中，根据数据范围选择合适方法即可。