跳转至

3288. 最长上升路径的长度

题目描述

给你一个长度为 n 的二维整数数组 coordinates 和一个整数 k ，其中 0 <= k < n 。

coordinates[i] = [xi, yi] 表示二维平面里一个点 (xi, yi) 。

如果一个点序列 (x1, y1), (x2, y2), (x3, y3), ..., (xm, ym) 满足以下条件，那么我们称它是一个长度为 m 的 上升序列 ：

  • 对于所有满足 1 <= i < m 的 i 都有 xi < xi + 1 且 yi < yi + 1 。
  • 对于所有 1 <= i <= m 的 i 对应的点 (xi, yi) 都在给定的坐标数组里。

请你返回包含坐标 coordinates[k] 的 最长上升路径 的长度。

 

示例 1：

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

输出：3

解释：

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

示例 2：

输入：coordinates = [[2,1],[7,0],[5,6]], k = 2

输出：2

解释：

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

 

提示：

  • 1 <= n == coordinates.length <= 105
  • coordinates[i].length == 2
  • 0 <= coordinates[i][0], coordinates[i][1] <= 109
  • coordinates 中的元素 互不相同 。
  • 0 <= k <= n - 1

解法

方法一

思考

二维点要严格 \(x\)、\(y\) 都递增，且必须经过给定点 \(k\)。\(n\le 10^5\)，对点做 \(O(n^2)\) 的 LIS 不可行。路径是「\(k\) 左侧的 LIS」加「\(k\) 右侧的 LIS」减一。

按 \(x\) 排序、\(y\) 用树状数组或二分维护 LIS；左侧只看严格小于 \(k\) 的点，右侧只看严格大于 \(k\) 的点。题面暂无实现代码，思考依此拆成两段二维 LIS。

1


1


1


1

评论