互联网产品做网站好还是小程序,软件源码购买一般在哪个网站,网络推广外包代理,wordpress 自适应菜单题目链接#xff1a;leetcode:矩阵中严格递增的单元格数 描述 给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat#xff0c;你可以选择任一单元格作为 起始单元格 。 从起始单元格出发#xff0c;你可以移动到 同一行或同一列 中的任何其他单元格#xff0c;但前提是目…题目链接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]最右边位置出度为0dp[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(vectorvectorint mat) {int n mat.size(), m mat[0].size();vectornode arr(n * m);dpnode demoe (dpnode){inf, 0, inf, 0};vectordpnode row(n, demoe), col(m, demoe);for(int i 0; i n;i){for(int j 0;j m;j){arr[i*mj] (node){mat[i][j], i, j};}} sort(arr.begin(), arr.end());int ans0;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;}
}; 若有什么错误欢迎指正^ _ ^ 。
