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. 提取关键点：

   • 首先，我们提取出 coordinates[k] 的坐标 (kx, ky)，这是必须包含在序列中的点。
   • 我们需要找到所有可以放在 (kx, ky) 之前或之后的点，使得序列满足严格递增的条件。

2. 排序：

   • 对 coordinates 数组进行排序。排序的规则是：
     • 首先按 x 坐标升序排列。
     • 如果 x 坐标相同，则按 y 坐标降序排列。
     • 这样排序的目的是为了在后续处理中，可以方便地筛选出满足条件的点。

3. 筛选有效点：

   • 遍历排序后的 coordinates，筛选出满足以下条件的点：
     • 点的 x 和 y 坐标都小于 (kx, ky)（可以放在 (kx, ky) 之前）。
     • 或者点的 x 和 y 坐标都大于 (kx, ky)（可以放在 (kx, ky) 之后）。
   • 这些点是可能构成包含 (kx, ky) 的上升序列的候选点。

4. 构建最长递增子序列（LIS）：

   • 对于筛选出的点，我们关注它们的 y 坐标。
   • 我们需要找到一个最长递增子序列（LIS），使得这些 y 坐标是严格递增的。
   • 使用贪心算法和二分查找来高效计算 LIS 的长度：
     • 维护一个数组 g，其中 g[i] 表示长度为 i+1 的 LIS 的最小末尾元素。
     • 对于每个点的 y 坐标，使用二分查找找到它在 g 中的插入位置：
       • 如果 y 大于 g 的所有元素，则扩展 g。
       • 否则，替换 g 中第一个大于或等于 y 的元素。
   • 这样，g 的长度就是 LIS 的长度。

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)
			}
		}
	}
	return len(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

def max_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]
    return len(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)