Reamdme

2713.Maximum-Strictly-Inreasing-Cells-in-a-Matrix

我们肯定是将所有的元素排序之后逐个处理。对于(i,j)考虑以它为结尾的递增序列可以多少长，必然会查看序列里它之前的元素，而前一个元素必然是在同一行或者同一列。所以我们只要在同行同列里查找所有比mat[i][j]小的位置(x,y)。以(x,y)为结尾的递增序列可以多少长，那么以(i,j)为结尾的递增序列长度就可以增加1。问题就转化为了递归或者动态规划。

接下来的问题是，如果扫描同行同列的所有元素，那么总的时间复杂度是o(MN*M)。事实上我们只需要查看同行（或者同列）里元素值恰好比mat[i][j]小的位置和对应的序列长度即可。所以我们给每行（以及每列）维护一个key有序的map，比如rows[i][v] = 3表示第三行里，以值为v的格子为结尾的递增序列的最大长度是3. 所以对于(i,j)，我们用prev(rows[i].lower_bound(mat[i][j])就能定位最后一个恰好比mat[i][j]`小的位置。

注意在对所有的rows[i]和cols[j]，初始化的时候添加一个{INT_MIN, 0}的key-val对，可以避免lower_bound出现越界。