2025-04-19：最长上升路径的长度。用go语言，给你一个长度为 n 的二维整数数组 coordinates 和一个整数 k

2025-04-19：最长上升路径的长度。用go语言，给你一个长度为 n 的二维整数数组 coordinates 和一个整数 k（满足 0 <= k < n）。

数组 coordinates 中的每个元素 coordinates[i] = [xi, yi] 表示二维平面上的一个点 (xi, yi)。

定义一个点序列 (x1, y1), (x2, y2), ..., (xm, ym) 为“上升序列”，当且仅当满足：

1.对于序列中的每一对相邻点，坐标的 x 和 y 都严格递增，即对所有 1 <= i < m，有 xi < xi+1 且 yi < yi+1；

2.且序列中的每个点都存在于给定的 coordinates 数组中。

请你计算并返回一个包含点 coordinates[k] 的“最长上升序列”的长度。

1 <= n == coordinates.length <= 100000。

coordinates[i].length == 2。

0 <= coordinates[i][0], coordinates[i][1] <= 1000000000。

coordinates 中的元素 互不相同 。

0 <= k <= n - 1。

输入：coordinates = [[3,1],[2,2],[4,1],[0,0],[5,3]], k = 1。

输出：3。

解释：

(0, 0) ，(2, 2) ，(5, 3) 是包含坐标 (2, 2) 的最长上升路径。

题目来自leetcode3288。

解决步骤

1. 1. 提取关键点：
   • • 首先，我们提取出 coordinates[k] 的坐标 (kx, ky)，这是必须包含在序列中的点。
   • • 我们需要找到所有可以放在 (kx, ky) 之前或之后的点，使得序列满足严格递增的条件。
2. 2. 排序：
   • • 对 coordinates 数组进行排序。排序的规则是：
     • • 首先按 x 坐标升序排列。
     • • 如果 x 坐标相同，则按 y 坐标降序排列。
     • • 这样排序的目的是为了在后续处理中，可以方便地筛选出满足条件的点。
3. 3. 筛选有效点：
   • • 遍历排序后的 coordinates，筛选出满足以下条件的点：
     • • 点的 x 和 y 坐标都小于 (kx, ky)（可以放在 (kx, ky) 之前）。
     • • 或者点的 x 和 y 坐标都大于 (kx, ky)（可以放在 (kx, ky) 之后）。
   • • 这些点是可能构成包含 (kx, ky) 的上升序列的候选点。
4. 4. 构建最长递增子序列（LIS）：
   • • 对于筛选出的点，我们关注它们的 y 坐标。
   • • 我们需要找到一个最长递增子序列（LIS），使得这些 y 坐标是严格递增的。
   • • 使用贪心算法和二分查找来高效计算 LIS 的长度：
     • • 维护一个数组 g，其中 g[i] 表示长度为 i+1 的 LIS 的最小末尾元素。
     • • 对于每个点的 y 坐标，使用二分查找找到它在 g 中的插入位置：
       • • 如果 y 大于 g 的所有元素，则扩展 g。
       • • 否则，替换 g 中第一个大于或等于 y 的元素。
   • • 这样，g 的长度就是 LIS 的长度。
5. 5. 计算最终结果：
   • • LIS 的长度加上 1（因为 (kx, ky) 本身也需要被计入序列）就是最终的最长上升序列的长度。

时间复杂度和空间复杂度

• • 时间复杂度：
  • • 排序：O(n log n)。
  • • 遍历和筛选点：O(n)。
  • • 构建 LIS：O(m log m)，其中 m 是筛选出的点的数量（m <= n）。
  • • 总时间复杂度：O(n log n)（因为排序是主要操作）。
• • 空间复杂度：
  • • 存储排序后的数组：O(n)。
  • • 存储 g 数组：O(m)（最坏情况下 m = n）。
  • • 总空间复杂度：O(n)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
    "sort"
    "cmp"
)

func maxPathLength(coordinates [][]int, k int)int {
    kx, ky := coordinates[k][0], coordinates[k][1]
    slices.SortFunc(coordinates, func(a, b []int)int {
        return cmp.Or(a[0]-b[0], b[1]-a[1])
    })

    g := []int{}
    for _, p := range coordinates {
        x, y := p[0], p[1]
        if x < kx && y < ky || x > kx && y > ky {
            j := sort.SearchInts(g, y)
            if j < len(g) {
                g[j] = y
            } else {
                g = append(g, y)
            }
        }
    }
    returnlen(g) + 1// 算上 coordinates[k]
}


func main() {
    coordinates := [][]int{{3,1},{2,2},{4,1},{0,0},{5,3}}
    k := 1
    results := maxPathLength(coordinates, k)
    fmt.Println(results)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from bisect import bisect_left

defmax_path_length(coordinates, k):
    kx, ky = coordinates[k]

    # 按x升序，x相同按y降序排序
    coordinates.sort(key=lambda p: (p[0], -p[1]))

    g = []

    for x, y in coordinates:
        # 保留与k点同方向的点（x,y都比kx,ky大 或 都比kx,ky小）
        if (x < kx and y < ky) or (x > kx and y > ky):
            idx = bisect_left(g, y)
            if idx < len(g):
                g[idx] = y
            else:
                g.append(y)

    # LIS长度+1，算上coordinates[k]
    returnlen(g) + 1


if __name__ == "__main__":
    coordinates = [[3,1],[2,2],[4,1],[0,0],[5,3]]
    k = 1
    result = max_path_length(coordinates, k)
    print(result)

·