矩阵中严格递增的单元格数

本文主要是介绍矩阵中严格递增的单元格数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：leetcode:矩阵中严格递增的单元格数
描述

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为起始单元格。
从起始单元格出发，你可以移动到同一行或同一列中的任何其他单元格，但前提是目标单元格的值严格大于当前单元格的值。
你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。
请你找出从某个单元开始访问矩阵所能访问的单元格的最大数量。
返回一个表示可访问单元格最大数量的整数。

其中：
m == mat.length
n == mat[i].length
1 <= m, n <= 10^5
1 <= m * n <= 10^5
-10^5 <= mat[i][j] <= 10^5

输入

mat = [[3,1,6],[-9,5,7]]

输出

4

PS：之前有事漏做了ε=(´ο｀*)))唉，今天补一下。

思路：
初看题目，位置(i, j)，只能移动到同行或同列中值严格比他大的位置。因此可以将这个矩阵根据每个位置间的可到达性建立一张拓扑图，所求的得到最大单元格访问数量的路线，必然是从拓扑图中某一个入度为0的位置出发到某一个出度为0的位置结束。根据这个特性，我们可以从入度为0或者出度为0的位置出发来计算最大单元格访问数量。
在这里我采用了从出度为0出发的思路，个人感觉更“顺”一点。

设从位置(i , j)出发的最大单元格访问数为dp[i][j]，(i, p)可表示所有同行中(i, j)可到达的位置，(q, j)可表示同列中(i , j)可到达的位置。那么dp[i][j] = max(max(dp[i][p]+1), max(dp[q][j]+1) ) 。从这里可以看出，要得到dp[i][j]，我们要算出同行中所有的dp[i][p]和同列中所有的dp[q][j]，所以我们要从拓扑图的右边往左边计算dp[i][j]（最右边位置出度为0，dp[i][j] = 1）。

如果能顺利建图，那么问题就简单了，但是这里矩阵可能出现一维的情况，那么建图的复杂度就为O(n^2)，对于n最大为1e5的情况显然会超时，所以还得优化思路。

不能建图，那就继续从小的只能往大的位置走这一特性入手，并从整体出发。只要我先计算了所有比位置(i, j)值大的位置的dp值，那么计算dp[i][j]所需的依赖——dp[i][p]和dp[q][j]，都已经算好了。现在有了dp[i][p]和dp[q][j]，就剩下max(dp[i][p])和max(dp[q][j])的计算。若每次都采用遍历的方法去计算max(dp[i][p])和max(dp[q][j])，总复杂度又回到了O(n^2)，仍需优化。

以max(dp[i][p])的计算为例，若有两个位置(i, j0)和(i, j1), 且mat[i][j0] = mat[i][j1] + 1(只要mat[i][j1]是第i行中仅次于mat[i][j0]的值就行了)，目前已知dp[i][j0]，那么(i, j1)的max(dp[i][p]) = dp[i][j0] + 1。因此我们可建立两个数组，一个保存每行的最大dp值，一个保存每列的最大dp值。虽然我们是按mat值从大到小计算dp值，能保证不少算东西，但行或列中可能会存在相同的值，会多算东西。所以对于每行/每列的最大dp值需要存两个，一个存最大dp值一个存次大dp值，且取得两个值所在位置的mat值不能相同。这样就只需要在计算时比较一下mat[i][j]是否等于最大值所在mat值就行了，若不等于则选择最大dp值，反之选次大dp值。

struct node
{int val, x, y;bool operator < (const node &o)const{return val > o.val;}
};
struct dpnode
{int val_0, cnt_0;int val_1, cnt_1;void update(int val, int cnt){if(val == val_0){if(cnt > cnt_0){cnt_0 = cnt;}}else {if(cnt > cnt_0){cnt_1 = cnt_0;val_1 = val_0;cnt_0 = cnt;val_0 = val;}else if(cnt > cnt_1){cnt_1 = cnt;val_1 = val;}}}
};
const int inf = -1e5 - 5;
class Solution {
public:int maxIncreasingCells(vector<vector<int>>& mat) {int n = mat.size(), m = mat[0].size();vector<node> arr(n * m);dpnode demoe = (dpnode){inf, 0, inf, 0};vector<dpnode> row(n, demoe), col(m, demoe);for(int i = 0; i < n;i++){for(int j = 0;j < m;j++){arr[i*m+j] = (node){mat[i][j], i, j};}} sort(arr.begin(), arr.end());int ans=0;int tmp_row, tmp_col;for(int i = 0;i < arr.size();i++){if(row[arr[i].x].val_0 != arr[i].val){tmp_row = row[arr[i].x].cnt_0 + 1;}else tmp_row = row[arr[i].x].cnt_1 + 1;if(col[arr[i].y].val_0 != arr[i].val){tmp_col =  col[arr[i].y].cnt_0 + 1;}else tmp_col = col[arr[i].y].cnt_1 + 1;if(tmp_col > tmp_row) tmp_row = tmp_col;row[arr[i].x].update(arr[i].val, tmp_row);col[arr[i].y].update(arr[i].val, tmp_row);}for(int i = 0;i < n;i++){ans = max(ans, row[i].cnt_0);}for(int j = 0;j < m;j++){ans = max(ans, col[j].cnt_0);}return ans;}
};