统计梯形的数目I-LeetCode

3623.统计梯形的数目I

🎯 问题描述

描述：
给定平面上的 $N$ 个点 points，其中 points[i] = [x_i, y_i]。
请你统计这些点能组成多少个梯形。
梯形的定义是：至少有一组对边平行，且另一组对边不平行（或者简单定义为有一组对边平行）。
在本题的特定语境下（基于代码逻辑推断），通常指上下底平行于 x 轴的梯形。
即：我们需要选择两条不同的水平线（y 坐标不同），每条线上至少选两个点，从而构成一个梯形。

说明：

• 这是一个组合数学结合哈希表计数的问题。

• 核心逻辑是：梯形由两条平行的底边组成。

• 如果一条水平线上有 $k$ 个点，那么这条线上可以形成 $C_k^2 = \frac{k(k-1)}{2}$ 条线段。

• 任意两条不同高度的线段都可以组成一个梯形。

• 利用前缀和思想优化计算过程。

• 示例：

• 示例 1：

输入：points = [[0,0],[1,0],[0,1],[1,1],[2,1]]
输出：3
解释：
- y=0 的线有 2 个点：[0,0], [1,0] -> 形成 1 条线段 (C(2,2)=1)
- y=1 的线有 3 个点：[0,1], [1,1], [2,1] -> 形成 3 条线段 (C(3,2)=3)
- 梯形数量 = (y=0的线段数) * (y=1的线段数) = 1 * 3 = 3

💻 解题思路

思路1：组合数学 + 前缀和优化

思路1：代码实现

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        mod = 10**9 + 7
        ans = 0
        s = 0  # s 表示“之前所有高度的线段总数”（即与当前边不同的边数）
        
        # 1. 统计每个高度（y坐标）上的点数
        count = Counter(p[1] for p in points)
        
        # 2. 遍历每个高度的点数
        for num in count.values():
            # 计算当前高度能形成的线段数量：C(num, 2)
            e_count = num * (num - 1) // 2
            
            # 如果当前高度能形成线段
            if e_count > 0:
                # 当前高度的每一条线段，都可以和之前所有高度的所有线段组成梯形
                # 新增梯形数 = 当前线段数 * 历史线段总数
                ans += s * e_count
                
                # 更新历史线段总数
                s += e_count
                
        return ans % mod

思路1：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是 points 的长度。
  • Counter 统计需要遍历一次数组，耗时 $O(N)$。
  • 遍历 count.values()，由于 y 坐标的种类最多为 $N$，所以也是 $O(N)$。
  • 总时间复杂度为 $O(N)$。
• 空间复杂度：$O(N)$
  • Counter 哈希表在最坏情况下存储 $N$ 个不同的 y 坐标。

思考

1. 几何转化：

   • 梯形需要两条平行的边。在坐标系中，最简单的平行边是水平线段（y 坐标相同）。
   • 要形成一个梯形，我们需要：
     • 在高度 $y_1$ 上选两个点，形成线段 $L_1$。
     • 在高度 $y_2$ 上选两个点，形成线段 $L_2$（$y_1 \neq y_2$）。
   • 这两条线段 $L_1$ 和 $L_2$ 天然平行，且位于不同高度，因此一定能构成一个梯形。

2. 组合计算：

   • 如果某一行有 $k$ 个点，从中选 2 个点的方案数是组合数 $C_k^2 = \frac{k(k-1)}{2}$。这就是代码中的 e_count。

3. 前缀和优化（核心逻辑）：

   • 我们需要计算所有不同高度线段对的乘积之和。
   • 假设高度 $h_1, h_2, ..., h_k$ 的线段数分别为 $c_1, c_2, ..., c_k$。
   • 总梯形数 = $\sum_{i < j} (c_i \times c_j)$。
   • 暴力计算需要双重循环 $O(K^2)$。
   • 优化方法：
     • 维护一个变量 s，表示当前遍历到的位置之前，所有线段数的总和（即 $c_1 + c_2 + ... + c_{i-1}$）。
     • 当遍历到第 $i$ 个高度时，新增的梯形数就是 $c_i \times s$。
     • 然后更新 s += c_i。
   • 这样可以将复杂度降低到 $O(K)$。

4. 取模运算：

   • 由于结果可能很大，需要在返回时取模 $10^9 + 7$。

5. 边界情况：

   • 点数少于 4 个：无法构成梯形，返回 0。
   • 所有点都在同一条直线上：只能形成线段，无法形成两条不同高度的边，返回 0。
   • 某一行只有 1 个点：无法形成线段，e_count 为 0，不影响结果。