leetcode 329. 矩阵中的最长递增路径

题目：329. 矩阵中的最长递增路径 - 力扣（LeetCode）
数据规模很小，排序就够了

1. struct Node {
2.     int x;
3.     int y;
4.     int val;
5.     Node* up = nullptr;
6.     Node* down = nullptr;
7.     Node* left = nullptr;
8.     Node* right = nullptr;
9.     int length = 0;
10.     Node(int _x, int _y, int _v) {
11.         x = _x;
12.         y = _y;
13.         val = _v;
14.     }
15. };
16. bool myComp(Node* a, Node* b) {
17.     return a->val < b->val;
18. }
19. class Solution {
20. public:
21.     int longestIncreasingPath(vector<vector<int>>& matrix) {
22.         vector<Node*> arr;
23.         int upIdx, leftIdx;
24.         for (int i = 0; i < matrix.size(); i++) {
25.             vector<int>& t = matrix[i];
26.             for (int j = 0; j < t.size(); j++) {
27.                 Node* node = new Node(i, j, t[j]);
28.                 arr.push_back(node);
29.                 if (i > 0) {
30.                     upIdx = (i - 1) * t.size() + j;
31.                     node->up = arr[upIdx];
32.                     arr[upIdx]->down = node;
33.                 }
34.                 if (j > 0) {
35.                     leftIdx = i * t.size() + j - 1;
36.                     node->left = arr[leftIdx];
37.                     arr[leftIdx]->right = node;
38.                 }
39.             }
40.         }
41.         sort(arr.begin(), arr.end(), myComp);
42.         int max;
43.         int ret = 1;
44.         for (int i = 0; i < arr.size(); i++) {
45.             Node* node = arr[i];
46.             max = 0;
47.             if (node->left && node->left->val < node->val && node->left->length > max) {
48.                 max = node->left->length;
49.             }
50.             if (node->right && node->right->val < node->val && node->right->length > max) {
51.                 max = node->right->length;
52.             }
53.             if (node->up && node->up->val < node->val && node->up->length > max) {
54.                 max = node->up->length;
55.             }
56.             if (node->down && node->down->val < node->val && node->down->length > max) {
57.                 max = node->down->length;
58.             }
59.             node->length = max + 1;
60.             if (node->length > ret) {
61.                 ret = node->length;
62.             }
63.         }
64.         return ret;
65.     }
66. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。