class Solution {
public:
int maxPathLength(vector<vector<int>>& coordinates, int k) {
}
};
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 <= 105coordinates[i].length == 20 <= coordinates[i][0], coordinates[i][1] <= 109coordinates 中的元素 互不相同 。0 <= k <= n - 1原站题解
golang 解法, 执行用时: 55 ms, 内存消耗: 20.6 MB, 提交时间: 2024-10-22 09:24:08
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]
}
python3 解法, 执行用时: 236 ms, 内存消耗: 57.7 MB, 提交时间: 2024-10-22 09:23:57
class Solution:
def maxPathLength(self, coordinates: List[List[int]], k: int) -> int:
kx, ky = coordinates[k]
coordinates.sort(key=lambda p: (p[0], -p[1]))
g = []
for x, y in coordinates:
if x < kx and y < ky or x > kx and y > ky:
j = bisect_left(g, y)
if j < len(g):
g[j] = y
else:
g.append(y)
return len(g) + 1 # 算上 coordinates[k]
java 解法, 执行用时: 69 ms, 内存消耗: 104 MB, 提交时间: 2024-10-22 09:23:35
class Solution {
public int maxPathLength(int[][] coordinates, int k) {
int kx = coordinates[k][0];
int ky = coordinates[k][1];
Arrays.sort(coordinates, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
List<Integer> g = new ArrayList<>();
for (int[] p : coordinates) {
int x = p[0];
int y = p[1];
if (x < kx && y < ky || x > kx && y > ky) {
int j = Collections.binarySearch(g, y); // g 没有重复元素，可以用 binarySearch
if (j < 0) {
j = -j - 1;
}
if (j < g.size()) {
g.set(j, y);
} else {
g.add(y);
}
}
}
return g.size() + 1; // 算上 coordinates[k]
}
// 数组
public int maxPathLength2(int[][] coordinates, int k) {
int kx = coordinates[k][0];
int ky = coordinates[k][1];
Arrays.sort(coordinates, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
int[] g = new int[coordinates.length];
int m = 0; // g 的长度
for (int[] p : coordinates) {
int x = p[0];
int y = p[1];
if (x < kx && y < ky || x > kx && y > ky) {
int j = Arrays.binarySearch(g, 0, m, y); // g 没有重复元素，可以用 binarySearch
if (j < 0) {
j = -j - 1;
}
if (j < m) {
g[j] = y;
} else {
g[m++] = y;
}
}
}
return m + 1; // 算上 coordinates[k]
}
}
cpp 解法, 执行用时: 116 ms, 内存消耗: 143.9 MB, 提交时间: 2024-10-22 09:23:05
class Solution {
public:
int maxPathLength(vector<vector<int>>& coordinates, int k) {
int kx = coordinates[k][0], ky = coordinates[k][1];
ranges::sort(coordinates, [](const auto& a, const auto& b) {
return a[0] < b[0] || a[0] == b[0] && a[1] > b[1];
});
vector<int> g;
for (auto& p : coordinates) {
int x = p[0], y = p[1];
if (x < kx && y < ky || x > kx && y > ky) {
auto it = ranges::lower_bound(g, y);
if (it != g.end()) {
*it = y;
} else {
g.push_back(y);
}
}
}
return g.size() + 1; // 算上 coordinates[k]
}
};