当前位置：首页 > ai >正文

【C++单调栈向量】3288最长上升路径的长度|2449

ai 2025/7/21 6:11:38

本文涉及的基础知识点

C++单调栈

LeetCode3288. 最长上升路径的长度

给你一个长度为 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 <= 10⁵
coordinates[i].length == 2
0 <= coordinates[i][0], coordinates[i][1] <= 10⁹
coordinates 中的元素互不相同。
0 <= k <= n - 1

单调向量

数字简称c。
性质一：如果x或y 等于c[k]则无论放在c[k]之前，还是c[k]之后都不行。故抛弃这些点。
性质二：同理性质一，x <c[k],且y > c[k] 也抛弃。
性质三：同理性质一，x >c[k],且y < c[k] 也抛弃。
余下的点分两种情况：
一，x,y皆小于c[k]，放到m1中。
二，x,y皆大于c[k]，放到m2中。
m1和m2都是map<int,vector> ，键是x，值是y的集合。
本题 $\iff$ m1的最长递增子序列长度 + 1 + m2的最长递增子序列长度。
处理m1或m2的函数如下：
for x1:m y1:m[x1]
v[i]记录x < x1，长度为i递增子序序列最后一个值的最小值，v={INT_MIN}。长度为i的子序列seq1,seq2，如果seq1的最后一个值小于seq2的最后一个值。则任意以seq2为前缀的递增序列，都可以替换为seq1，仍然递增。故无需记录seq2。
i = lower(v,y1) -v.begin() 表明长度为[0…i-1]的子序列都可以加上y1，长度变成[1…i]。v[0…i-1] < y，无需更改。故只需要更改v[i]=y。
注意：i 等于v.size()则追加。
将{y,i}缓存起来，m[x1]遍历完后，统一修改v。否则子序列中可能有相同的x。
返回v.size()-1

代码

核心代码

class Solution {public:int maxPathLength(vector<vector<int>>& coordinates, int k) {map<int, vector<int>> m1, m2;for (const auto& v : coordinates) {if ((v[0] < coordinates[k][0]) && (v[1] < coordinates[k][1])) {m1[v[0]].emplace_back(v[1]);}if ((v[0] > coordinates[k][0]) && (v[1] > coordinates[k][1])) {m2[v[0]].emplace_back(v[1]);}}auto Do = [&](const map<int, vector<int>>& m) {vector<int> v = { INT_MIN / 2 };for (const auto& [x, v1]:m) {vector<pair<int,int>> change;for (const auto& y : v1) {auto inx = lower_bound(v.begin(), v.end(), y)-v.begin();change.emplace_back(inx, y);}for (const auto& [i, y] : change) {if (i >= v.size()) { v.emplace_back(y); }else { v[i] = min(v[i], y); }}}return v.size() - 1;};return Do(m1) + 1 + Do(m2);}};

单元测试

	vector<vector<int>>coordinates;int k;TEST_METHOD(TestMethod1){coordinates = { {3,1},{2,2},{4,1},{0,0},{5,3} }, k = 1;auto res = Solution().maxPathLength(coordinates, k);AssertEx(3, res);}TEST_METHOD(TestMethod2){coordinates = { {2,1},{7,0},{5,6} }, k = 2;auto res = Solution().maxPathLength(coordinates, k);AssertEx(2, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功