一道后缀排序题的降维打击

题目

给你两个长度均为 n 的整数数组 nums 和 target。

对于每个下标 i，考虑将原数组的后缀 nums[i…n - 1] 按非递增顺序排序。

返回使排序后的数组等于 target 的下标 i 的数量。

法 1：模拟（TLE）

先写一个模拟的吧。之后或许还能够改进。

class Solution:
    def countSuffix(self, nums: list[int], target: list[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            if nums[:i] + (sorted(nums[i:],reverse = True)) == target:
                ans += 1
        return ans

完全按照题意写的方法，非常暴力啊。当然，先写出一个完全正确的模拟（哪怕会超时）解法是很正常的，因为在后续进行优化之后，它可以验证优化后的代码对不对。

分析其时间复杂度，为 $O(N^2logN)$ ，主要消耗在排序、切片、比对上了，唉，果不其然 TLE 了。那么我们之后的入手点就是这两个，是否可以“不多次排序”也能得出结果？

法 2：从前往后，从后往前（Gemini）

因为对 nums 的后半段进行了降序排序，所以排序完出来的东西必然是非递增的。

这就意味着，如果能匹配成功，target 的后半段自己也必须本来就是非递增的。通过一个从后往前的循环可以确定从哪开始非递增，达到时间上的 $O(N)$ 。

imin = 0
for i in range(len(nums) - 1, 0, -1):
    if target[i - 1] < target[i]:
        imin = i
        break

i 左边的前缀是不能动的，所以 nums 和 target 在 i 之前必须长得一模一样。我们要从前往后扫描，找出它们在哪一个索引第一次“分道扬镳”了。时间复杂度仍然为 $O(N)$ 。

imax = len(nums) - 1
for i in range(len(nums)):
    if nums[i] != target[i]:
        imax = i
        break

是不是在 imin 和 imax 之间的每一个 i 都一定合法呢？不一定。我们前面提到过，虽然在这个区间里前缀对得上、后缀也降序，但我们还没检查“后缀的数字种类和数量（词频）是不是完全一样”。这个也好说，来一个 Counter 即可。

ans = 0
cnt = defaultdict(int)
nonzero_keys = 0

for j in range(imax + 1, n): # 针对 imax 之后的部分，只维护 Counter
    if cnt[nums[j]] == 0: nonzero_keys += 1 
    cnt[nums[j]] += 1
    if cnt[nums[j]] == 0: nonzero_keys -= 1
    if cnt[target[j]] == 0: nonzero_keys += 1 # 从 0 变成非 0 (负数值也是非0)，非零键增加
    cnt[target[j]] -= 1
    if cnt[target[j]] == 0: nonzero_keys -= 1

for i in range(imax, imin - 1, -1): # 针对答案区间的部分，在维护 Counter 的同时判断是否能够成为答案
    if cnt[nums[i]] == 0: nonzero_keys += 1
    cnt[nums[i]] += 1
    if cnt[nums[i]] == 0: nonzero_keys -= 1
    if cnt[target[i]] == 0: nonzero_keys += 1
    cnt[target[i]] -= 1
    if cnt[target[i]] == 0: nonzero_keys -= 1
    if nonzero_keys == 0:
        ans += 1

法 3：真的需要再维护 Counter 吗？（灵神）

如果我们在一开始的时候针对两个 list 进行统计，两者一致，那么可以把 list 分为前缀和后缀。

前缀部分已经一一对应，则后缀部分每个元素的出现次数都在 nums 和 target 保持一致。后缀部分又统一按照非升序排列，则后缀部分的元素和位置都会在 nums 和 target 保持一致。也就是说，Gemini 解法中的 Counter 部分可以直接在开始的时候用

1 2	if Counter(nums) != Counter(target): return 0

完成判断和剪枝。

最后的解法是：

class Solution:
    def countSuffix(self, nums: list[int], target: list[int]) -> int:
        imax = len(nums) - 1
        imin = 0
        # 首先如果数字都对应不上排序之后显然不能结合到一起，先剪枝
        if Counter(nums) != Counter(target):
            return 0
        # 然后 i 肯定小于某个数，否则前缀对不上（eg: 123[4]... 123[3]...）不需要考虑后缀了
        for i in range(len(nums)):
            if nums[i] != target[i]:
                imax = i
                break
        # 最后 target 的后缀也得是非递增的，i 肯定大于某个数，否则 nums 后面在递减而 target 还在递增
        for i in range(len(nums) - 1, 0, -1):
            if target[i - 1] < target[i]:
                imin = i
                break
        return max(0, imax - imin + 1)

不建议将文章内容用于训练 LLM，以免影响语料质量。本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。