【map】【动态规划】LeetCode2713:矩阵中严格递增的单元格数

本文涉及的基础知识点

二分查找算法合集

题目

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为起始单元格。
从起始单元格出发，你可以移动到同一行或同一列中的任何其他单元格，但前提是目标单元格的值严格大于当前单元格的值。
你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。
请你找出从某个单元开始访问矩阵所能访问的单元格的最大数量。
返回一个表示可访问单元格最大数量的整数。
示例 1：
输入：mat = [[3,1],[3,4]]
输出：2
解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。
示例 2：
输入：mat = [[1,1],[1,1]]
输出：1
解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。
示例 3：
输入：mat = [[3,1,6],[-9,5,7]]
输出：4
解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。
参数范围：
m == mat.length
n == mat[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
-10⁵ <= mat[i][j] <= 10⁵

分析

时间复杂度: O(mnlogmn)。初始化数据时间复杂度：O(nmlogmn)。枚举所有单元格时间复杂度O(mn)，处理每个单元格，时间复杂度O(n)。

变量解析


mValueToRowCols	各值对应的行列，按值降序排序
vRowMax	大于当前值的各行最大递增单元格数
vColMax	大于当前值的各列最大递增单元格数
vBuf	当前值各行列的最大递增单元格数

代码

class Solution {
public:
	int maxIncreasingCells(vector<vector<int>>& mat) {
		m_r = mat.size();
		m_c = mat.front().size();
		std::map<int, vector<pair<int, int>>,greater<int>> mValueToRowCols;
		for (int r = 0; r < m_r ;r++)
		{
			for (int c = 0; c < m_c ; c++)
			{
				mValueToRowCols[mat[r][c]].emplace_back(r, c);
			}
		}
		vector<int> vRowMax(m_r), vColMax(m_c);
		vector<tuple<int, int, int>> vBuf;
		for (const auto& [tmp, v] : mValueToRowCols)
		{			
			for (const auto& [r, c] : v)
			{
				const int iMax = max(vRowMax[r], vColMax[c]) + 1;
				vBuf.emplace_back(r, c, iMax);				
			}
			for (const auto& [r, c, iMax] : vBuf)
			{
				vRowMax[r] = max(vRowMax[r], iMax);
				vColMax[c] = max(vColMax[c], iMax);
			}
			vBuf.clear();
		}
		return *std::max_element(vRowMax.begin(), vRowMax.end());
	}
	int m_r, m_c;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	vector<vector<int>> mat;
	{
		Solution slu;
		mat = { {3,1},{3,4} };
		auto res = slu.maxIncreasingCells(mat);
		Assert(2, res);
	}
	{
		Solution slu;
		mat = { {1,1},{1,1} };
		auto res = slu.maxIncreasingCells(mat);
		Assert(1, res);
	}
	{
		Solution slu;
		mat = mat = { {3,1,6},{-9,5,7} };
		auto res = slu.maxIncreasingCells(mat);
		Assert(4, res);
	}
	{
		Solution slu;
		mat = mat = { {5, 2, 9},{-6, 2, -5},{-1, 0, -5} };
		auto res = slu.maxIncreasingCells(mat);
		Assert(6, res);
	}
}

超时代码示例

vector<int> vRowMax(m_r), vColMax(m_c);
		for (const auto& [tmp, v] : mValueToRowCols)
		{
			vector<int> vCurRowMax = vRowMax, vCurColMax = vColMax;
			for (const auto& [r, c] : v)
			{
				const int iMax = max(vRowMax[r], vColMax[c]) + 1;
				vCurRowMax[r]= max(vCurRowMax[r],iMax);
				vCurColMax[c] = max(vCurColMax[r],iMax);
			}
			vCurRowMax.swap(vRowMax);
			vCurColMax.swap(vColMax);
		}

vector 构造函数比较费事，执行mn次会超时。

2023年6月旧代码

class Solution {
public:
int maxIncreasingCells(vector<vector>& mat)
{
m_r = mat.size();
m_c = mat[0].size();
std::map < int, vector<pair<int, int>>,std::greater> mValueRowCol;
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
mValueRowCol[mat[r][c]].emplace_back(make_pair( r, c ));
}
}
vector vPreRows(m_r, 0), vPreCols(m_c, 0);
int iMaxRet = 0;
std::queue<std::tuple<int, int, int> > que;
for ( auto it : mValueRowCol)
{
for (const auto& pr : it.second)
{
int iRet = std::max(vPreRows[pr.first],vPreCols[pr.second])+1 ;
iMaxRet = max(iMaxRet, iRet);
que.emplace(pr.first, pr.second, iRet);
}
while (que.size())
{
const int r = get<0>(que.front());
const int c = get<1>(que.front());
const int iRet = get<2>(que.front());
que.pop();
vPreRows[r] = max(vPreRows[r] ,iRet);
vPreCols[c] = max(vPreCols[c],iRet);
}
}

	return iMaxRet;
}
int m_r, m_c;

};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛