目录
前言
2815. 数组中的最大数对和 – 力扣（LeetCode）
复杂度分析
3623. 统计梯形的数目 I – 力扣（LeetCode）
复杂度分析
总结
前言
今天我们来刷两道数据结构的题目。
2815. 数组中的最大数对和 – 力扣（LeetCode）
给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和 最大 的一对数，且这两个数数位上最大的数字相等。
返回最大和，如果不存在满足题意的数字对，返回 -1 。
这道题目我们可以根据灵神的思路，六个字：“枚举右，维护左”。
我们可以自己写一个函数用来求一个数数位上的最大值。初始化一个map，key设为数位上的最大值，value设为数位上最大值相同时的最大值。从左到右遍历nums数组，如果map中有最大数位和相同的元素，那么就更新ans，这样我们只需要一次遍历就可以解决这道题。
代码如下：
func maxSum(nums []int) int {
ans := -1 // ans设为-1，如果没更新过就直接返回
cnt := map[int]int{}
for _, x := range nums {
if j, ok := cnt[maxN(x)]; ok { // 如果cnt中存在一个元素和当前元素数位上的最大值相同
ans = max(ans, j+x) // 就更新ans
}
cnt[maxN(x)] = max(x, cnt[maxN(x)]) // 将cnt中存放的数更新为数位上的最大值相同时的最大的值
}
return ans // 返回ans
}
func maxN(n int) int { // 用来求数位上的最大值
ans := 0
for n > 0 {
ans = max(ans, n%10)
n /= 10
}
return ans
}
复杂度分析
- 时间复杂度：O(nlogU)，其中 n 为 nums 的长度，U=max(nums)。
- 空间复杂度：O(1)。仅用到若干额外变量。
3623. 统计梯形的数目 I – 力扣（LeetCode）
给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。
水平梯形 是一种凸四边形，具有 至少一对 水平边（即平行于 x 轴的边）。两条直线平行当且仅当它们的斜率相同。
返回可以从 points 中任意选择四个不同点组成的 水平梯形 数量。
由于答案可能非常大，请返回结果对 109 + 7 取余数后的值。
这道题目乍一看还挺复杂的，需要选四个点组成梯形。但我们仔细分析一下就会发现，水平梯形的关键在于有一对平行于 x 轴的边，也就是说至少要有两对点的 y 坐标相同。
我们可以换个思路：先统计每个 y 坐标上有多少个点，然后在不同的 y 坐标上各选两个点，这样就能组成一个梯形。具体来说：
- 在 y1 上选2个点
- 在 y2 上选2个点（y1 ≠ y2）
- 这4个点就能构成一个水平梯形
我们用 cnt 来统计每个 y 坐标的点数，然后从某个 y 坐标选2个点的方案数就是组合数 C(n, 2) = n * (n-1) / 2。接下来就是计数问题了：我们遍历每个 y 坐标，当前 y 上的选法数量是 cur，之前所有 y 上的选法数量总和是 last，那么当前贡献就是 cur * last（相乘就是从两个不同 y 各选一对点的方案数）。
代码如下：
func countTrapezoids(points [][]int) int {
const mod = 1000000007
ans := 0
cnt := map[int]int{}
for _, p := range points {
cnt[p[1]]++ // 统计每个y坐标有多少个点
}
last := 0
for _, v := range cnt {
cur := v * (v-1) / 2 // 当前y坐标上选2个点的组合数
ans += cur * last // 当前y和之前所有y的配对数
last += cur // 累加到last中
}
return ans % mod // 最后取模返回
}
这样我们只需要遍历一次 points 统计 y 坐标，再遍历一次 cnt 计算答案，时间复杂度是 O(n)，非常高效。
复杂度分析
- 时间复杂度：O(n)，其中 n 是 points 的长度。
- 空间复杂度：O(n)。
总结
枚举右，维护左。这个思想是非常重要的，可以将统计两个元素的问题转化成统计一个元素，然后回头找符合要求的元素这类问题，因此非常高效。
如果我的内容对你有帮助，请点赞，评论，收藏。创作不易，大家的支持就是我坚持下去的动力！
