240. 搜索二维矩阵II
题目的内容是，给定一个 m×n 的矩阵，搜索一个目标值 target，返回 bool 值。这个矩阵的特点是：
- 每一行的元素从左到右升序排列
- 每一列的元素从上到下升序排列
一开始我以为，这个题目太简单了，这个不是直接写就好了嘛，我只要遍历就好了啊，如果当前元素小于 target，就遍历右侧元素，如果遇到大于 target 的元素，就向下遍历，如果还是大于 target 就向左遍历，总是会找到的。
不过这个自然而然的想法，却是不对的。我写了三遍也没写对自己的这个想法。感觉自己太蠢了。然后我看了看题解，才发现竟然如此简单，可是我竟然连最简单的解法也没做出来。自己想了一个莫名其妙的遍历算法，既不是最简单的解法，也不是最巧妙的解法。
我想，可能是做了一定数量的题目后，我就失去了初心，总觉得自己有点积累了，可以一下找到最高效最简单的解了。
如果，我们抛弃一切技巧，按部就班暴力解题，怎么解呢？当然是从左到右，从上到下，逐一遍历，直到遍历完毕或者找到目标。这才是正确的遍历方法。也是最自然而然，基本没学过算法的人应该能想到的算法，也显然是一个正确的算法。
- m == matrix.length
- n == matrix[i].length
- 1 <= n, m <= 300
- -109 <= matrix[i][j] <= 109
- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
- -109 <= target <= 109
从题目的约束来看，这种暴力扫描法，复杂度 O(mn)，最大也才 9 万的规模。可是我花了 2 个小时，也没想到这么去做。其实，解算法题，你的初心是把题目做对，做对后，再来讨论效率优化。想到了乔帮主的 stay foolish，才有点明白，为啥这时候就不能 stay foolish 呢？
如果，我们要提高算法的效率怎么做呢？题目的一个条件是，有序，搜索有序，自然而然就要想到二分查找，所以，我们在每个横行里，进行二分查找，那么在单行遍历，时间复杂度会降到 O(logn)，总复杂度降到 O(mlogn)，在大多数简单算法题给定的规模里，这个复杂度都足够应付了。
最后，如果我们还想优化，还有办法么？最后这个办法，可能是唯一不是普通人，随便就能想到的办法，如果一下点醒你，你会秒懂，但是没戳破就觉得真的想不到。我自己也没想明白。我怎么也想不到，如何才能按部就班想出这样的解题法。
其实有个数学家说过。如果你解不出一道题目，一定是你还没有充份利用好已知条件。好像认真看已知条件就一定能找到破解之法，但是没那么简单。比如这道题目，我们想出二分法，就是利用了有序，这个条件。但是，显然这题目给出了两个有序。从左到右，从上到下都是有序的。
二维矩阵的例子
同时利用两个有序的方法，显然也是一个解法，就是没那么容易想到。而且，这是一个二维的矩阵。这个方法就是，我们遍历的时候，不一定从左上角开始遍历。而是从左下角或者右上角开始遍历。
程序员的思维定势是从左上角开始，当然也有一部分倒序的，那也会选择右下。但是能想到另外两个角，是要有怎样的经验和知识才能让你想到呢？这是我唯一的疑问。
以左下角为例，当你从左下角出发的时候，你发现，你上面的数字都比当前数字小，你右侧的数字都比当前大。右上角同理，其实左下角和右上角的数字，相当于所有数字的中间位置。
当前位置太小，就往右，太大就往上，循环往复，就会找到目标，或者结束遍历：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
if m == 0: return False
n = len(matrix[0])
if n == 0: return False
x, y = m - 1, 0
while matrix[x][y] != target:
if matrix[x][y] > target:
if x - 1 >= 0:
x -= 1
else:
return False
else:
if y + 1 < n:
y += 1
else:
return False
return True
这个算法的时间复杂度是O(m+n)，是已经分析过的算法里，复杂度最低的算法了。这题目说透了，就觉得太简单了。但是难点在于你就是想不到这里来。这题目给我一个最大的提醒，就是做题不要好高骛远，而是总要先想一个笨办法立于不败之地，再思考怎么优化，才是比较妥帖的做题态度。