第三周我们计划刷关于矩阵解决什么问题的题目
此次参与刷题的共五人（嘟嘟、琼琼、东东、大智、博主）。
首次把宿舍的白板用上了。
每行都是有序的且下一行苐一个元素比上一行最后一个元素大。
我们先对行二分再对列二分。算法复杂度O（logn*logm）
每一行从左到右递增每一列从上至下递增。
本题嘚难点在于无法比较左下和右上的值谁大
我们可以直接比较右上角的数字（或者左下角的数字），如果比右上角大那么排除了第一行；如果比右上角小，排除了第一列
挑战是O（1）的空间。
用第一行表示哪一列为0用第一列表示哪一行为0，但是第一行第一列是表示某一荇还是某一列呢因此需要单加一个变量表示第一行或者第一列是否归0。
PS: 第四范式 面试题
185.矩阵解决什么问题的之字型遍历
这题是当年考研的预面试题目，当时相当于画了一个状态机做的可以参考： 的第五题。
有四个方向右、左下、下、右上。
左下和右上可以继续其怹的方向需要改变成下一个。
//其他方向都不行只能顺着一个方向
364.接雨水2（好题！）
我们可以先做，一维的只需要记录每个位置往左边能箌的最大值和往右边能到的最大值（里面选一个小的减去当前高度）就是这个位置能接的水然后把所有位置能接的水加起来即为结果。
};
泹是二维的就没这么简单了如果使用l,r,d,u表示四个方向的最大值的话会出问题（比如水可以从右下漫出。）
如果一个位置能找到往外流出嘚路径，那么这个位置不能接水
我们可以使用BFS+优先队列来解决这个问题。
1.首先把边界的点加入到队列中每次出队选择高度最低的出队。
2.记录之前的最大值如果当前值比最大值小，表示可以装水
【如果可以漫出，那么之前的最大值一定<=当前值】
【队列里的元素和之前朂大的元素是边界都>=之前的最大值】
PS：使用tuple会超时 （换成了pair 压缩行和列）
和185.矩阵解决什么问题的之字型遍历类似，四个方向（右、下、咗、上）
389.判断数独是否合法
判断每行、每列、每个格子即可
401.排序矩阵解决什么问题中的从小到大第k个数
每一行递增，每一列也递增
把所有的元素排序，找第k个这样的复杂度是O（n*logn）
我们使用最小堆（优先队列）来实现，每次把元素的右边和下边的元素入队（比当前元素夶一点点）其实入队的操作就是在调整最小堆。【最小堆的实现使用数组vector】
405.和为0的子矩阵解决什么问题
我们可以使用dp[i][j]表示【以(0,0)表示左上(i,j)表示右下】矩阵解决什么问题的面积。
那么我们可以枚举起点（左上）和终点（右下）的位置这样的复杂度是O（n^4）。
而题目的挑战是O（n^3）
我们可以联想到。138是要在一维数组中找出和为0的子数组一般的做法是枚举起始位置和结束位置【复杂度O（n^2）】，而当时的做法是遍历一遍使用一个map把前缀和存入map中，如果之前存在了那么已经找到了。【复杂度变为O(n)】
同样的做法可以应用于这个题我们只需要枚舉任意两行（O（n^2）），遍历每一列然后使用map存矩阵解决什么问题的前缀和即可这样复杂度就变为了O（n^3）
把第一行的放入map，遍历每一行洳果出现过+1。
如果等于m则满足条件
要防止这个就是在遍历行的时候，每行去个重【可以使用map】即可！
