3288. 最长递增路径的长度

Hard

题目描述

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

coordinates[i] = [xi, yi] 表示二维平面上的点 (xi, yi)。

长度为 m 的递增路径定义为一个点的列表 (x1, y1), (x2, y2), (x3, y3), ..., (xm, ym)，满足：

对于所有 1 <= i < m，都有 xi < xi+1 且 yi < yi+1
对于所有 1 <= i <= m，(xi, yi) 都在给定的 coordinates 中

返回包含 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 <= 10^5
coordinates[i].length == 2
0 <= coordinates[i][0], coordinates[i][1] <= 10^9
coordinates 中所有元素都不相同
0 <= k <= n - 1

解题思路

这道题的核心思想是将问题分解为两部分：

在 coordinates[k] 之前的最长递增子序列
在 coordinates[k] 之后的最长递增子序列

解题步骤：

分离点集：将坐标分为三部分
- 严格小于 coordinates[k] 的点（x和y都小）
- coordinates[k] 本身
- 严格大于 coordinates[k] 的点（x和y都大）
排序策略：
- 对于"小于"的点：按x升序排列，x相同时按y降序排列
- 对于"大于"的点：按x升序排列，x相同时按y降序排列
- 这样的排序保证了在计算LIS时，x坐标的约束已经满足，只需关注y坐标
计算LIS：
- 对排序后的y坐标序列计算最长递增子序列
- 使用二分搜索优化，时间复杂度O(n log n)
合并结果：
- 最终答案 = 前面的LIS长度 + 1（coordinates[k]本身）+ 后面的LIS长度

关键洞察：通过特殊的排序方式，将二维递增路径问题转化为一维LIS问题。

代码实现

class Solution {
public:
    int maxPathLength(vector<vector<int>>& coordinates, int k) {
        int target_x = coordinates[k][0], target_y = coordinates[k][1];
        
        vector<int> before, after;
        
        // 分离点集
        for (auto& coord : coordinates) {
            if (coord[0] < target_x && coord[1] < target_y) {
                before.push_back(coord[1]);
            } else if (coord[0] > target_x && coord[1] > target_y) {
                after.push_back(coord[1]);
            }
        }
        
        // 对before按x升序，y降序排序（这里只需要y值，已经按需求处理）
        vector<vector<int>> before_points, after_points;
        for (auto& coord : coordinates) {
            if (coord[0] < target_x && coord[1] < target_y) {
                before_points.push_back(coord);
            } else if (coord[0] > target_x && coord[1] > target_y) {
                after_points.push_back(coord);
            }
        }
        
        sort(before_points.begin(), before_points.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
        });
        
        sort(after_points.begin(), after_points.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
        });
        
        before.clear();
        after.clear();
        for (auto& p : before_points) before.push_back(p[1]);
        for (auto& p : after_points) after.push_back(p[1]);
        
        return lengthOfLIS(before) + 1 + lengthOfLIS(after);
    }
    
private:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> dp;
        for (int num : nums) {
            auto it = lower_bound(dp.begin(), dp.end(), num);
            if (it == dp.end()) {
                dp.push_back(num);
            } else {
                *it = num;
            }
        }
        return dp.size();
    }
};

class Solution:
    def maxPathLength(self, coordinates: List[List[int]], k: int) -> int:
        target_x, target_y = coordinates[k]
        
        before_points = []
        after_points = []
        
        # 分离点集
        for x, y in coordinates:
            if x < target_x and y < target_y:
                before_points.append([x, y])
            elif x > target_x and y > target_y:
                after_points.append([x, y])
        
        # 排序：x升序，x相同时y降序
        before_points.sort(key=lambda p: (p[0], -p[1]))
        after_points.sort(key=lambda p: (p[0], -p[1]))
        
        # 提取y坐标
        before_y = [p[1] for p in before_points]
        after_y = [p[1] for p in after_points]
        
        return self.lengthOfLIS(before_y) + 1 + self.lengthOfLIS(after_y)
    
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        
        from bisect import bisect_left
        dp = []
        
        for num in nums:
            pos = bisect_left(dp, num)
            if pos == len(dp):
                dp.append(num)
            else:
                dp[pos] = num
        
        return len(dp)

public class Solution {
    public int MaxPathLength(int[][] coordinates, int k) {
        int targetX = coordinates[k][0], targetY = coordinates[k][1];
        
        var beforePoints = new List<int[]>();
        var afterPoints = new List<int[]>();
        
        // 分离点集
        foreach (var coord in coordinates) {
            if (coord[0] < targetX && coord[1] < targetY) {
                beforePoints.Add(coord);
            } else if (coord[0] > targetX && coord[1] > targetY) {
                afterPoints.Add(coord);
            }
        }
        
        // 排序：x升序，x相同时y降序
        beforePoints.Sort((a, b) => a[0] != b[0] ? a[0].CompareTo(b[0]) : b[1].CompareTo(a[1]));
        afterPoints.Sort((a, b) => a[0] != b[0] ? a[0].CompareTo(b[0]) : b[1].CompareTo(a[1]));
        
        // 提取y坐标
        var beforeY = beforePoints.Select(p => p[1]).ToArray();
        var afterY = afterPoints.Select(p => p[1]).ToArray();
        
        return LengthOfLIS(beforeY) + 1 + LengthOfLIS(afterY);
    }
    
    private int LengthOfLIS(int[] nums) {
        if (nums.Length == 0) return 0;
        
        var dp = new List<int>();
        
        foreach (int num in nums) {
            int pos = BinarySearch(dp, num);
            if (pos == dp.Count) {
                dp.Add(num);
            } else {
                dp[pos] = num;
            }
        }
        
        return dp.Count;
    }
    
    private int BinarySearch(List<int> list, int target) {
        int left = 0, right = list.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var maxPathLength = function(coordinates, k) {
    const target = coordinates[k];
    
    // Find longest increasing subsequence ending at target
    const before = [];
    const after = [];
    
    for (let i = 0; i < coordinates.length; i++) {
        const [x, y] = coordinates[i];
        if (x < target[0] && y < target[1]) {
            before.push([x, y]);
        } else if (x > target[0] && y > target[1]) {
            after.push([x, y]);
        }
    }
    
    function lis(points) {
        if (points.length === 0) return 0;
        
        points.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
        
        const dp = [];
        
        for (const [x, y] of points) {
            let left = 0, right = dp.length;
            while (left < right) {
                const mid = Math.floor((left + right) / 2);
                if (dp[mid] < y) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if (left === dp.length) {
                dp.push(y);
            } else {
                dp[left] = y;
            }
        }
        
        return dp.length;
    }
    
    return lis(before) + 1 + lis(after);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大O表示法
时间复杂度	O(n log n)
空间复杂度	O(n)

其中 n 是坐标数组的长度。时间复杂度主要来自排序操作和LIS计算，空间复杂度用于存储分离后的点集和LIS数组。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析