统计输入中的极小向量问题：求解思路与优化问询

问题分析与高效解法 #

首先明确题目中的极小向量定义：向量 v 是极小向量，当且仅当不存在其他向量 u（u≠v），使得 u 的每一个分量都小于等于 v 的对应分量（即 u 支配 v）。

针对 n≤100000 的规模，必须采用时间复杂度为 O(n log n) 的算法才能在1秒内完成，以下是具体步骤：

1. 去重预处理

重复的向量必然不是极小向量（因为彼此支配），所以第一步先移除所有重复向量。可以将向量转换为不可变类型（如元组），通过集合去重，再转回列表。

2. 排序优化

对去重后的向量进行排序，排序规则为：

• 按第1个分量升序排列；
• 若第1个分量相等，按第2个分量升序排列；
• 以此类推，直到第k个分量（k为向量维度）。

排序后，前面的向量字典序≤后面的向量，这意味着后面的向量不可能支配前面的向量（因为至少有一个分量更大），我们只需判断当前向量是否被前面的向量支配即可。

3. 单调栈筛选极小向量

维护一个候选列表（单调栈结构），存储已确定的极小向量，确保列表中向量的后续分量（从第2个到第k个）严格递减。遍历排序后的向量时：

• 若当前向量的最后一个分量小于候选列表末尾向量的最后一个分量，说明它不会被任何候选向量支配（因为候选列表后续分量递减，所有候选向量的后续分量都大于当前向量），将其加入候选列表；
• 否则，当前向量被某个候选向量支配，跳过。

最终候选列表的长度就是极小向量的数量。

为什么你的初始思路低效？ #

你提到用 Result 类重载运算符加小顶堆的思路，核心问题在于：

• 小顶堆只能维护单一“最小”元素，无法直接统计所有极小向量；
• 若要逐个判断每个向量是否为极小向量，需要与所有其他向量比较，时间复杂度高达 O(n²)，完全无法应对 n=1e5 的规模；
• 堆操作的额外开销也远大于排序后线性遍历的效率。

代码示例（二维向量） #

def count_min_vectors(vectors):
    # 去重：转换为元组后用集合去重
    unique_vecs = list(set(tuple(v) for v in vectors))
    if not unique_vecs:
        return 0
    
    # 按第一个分量升序，第二个分量升序排序
    unique_vecs.sort(key=lambda x: (x[0], x[1]))
    
    candidates = []
    for vec in unique_vecs:
        # 利用单调栈特性，只需与末尾元素比较
        while candidates:
            last = candidates[-1]
            if last[1] <= vec[1]:
                # last的两个分量都≤当前向量，当前向量被支配
                break
            else:
                # 当前向量的第二个分量更小，不会被任何候选向量支配
                candidates.append(vec)
                break
        else:
            # 候选列表为空，直接加入
            candidates.append(vec)
    
    return len(candidates)

该代码的时间复杂度为 O(n log n)（去重+排序），加上线性遍历的 O(m)（m 为去重后向量数量），完全满足时间限制。

推广到k维向量 #

对于k维向量，排序规则保持不变，筛选时维护候选列表中向量的第2到k个分量严格递减。遍历过程中，只需比较当前向量的最后一个分量与候选列表末尾向量的最后一个分量：若更小则加入，否则跳过，逻辑与二维情况一致。

内容的提问来源于stack exchange，提问作者bordus