面试题|面试题——寻找矩阵中的极小值面试题|李明徽的算法

AcWing 1452 寻找矩阵的极小值题目 【面试题|面试题——寻找矩阵中的极小值】给定一个n×n的矩阵，矩阵中包含n×n个_互不相同_的整数。
定义极小值：如果一个数的值比与它相邻的所有数字的值都小，则这个数值就被称为极小值。
一个数的相邻数字是指其上下左右四个方向相邻的四个数字，另外注意，处于边界或角落的数的相邻数字可能少于四个。
要求在O(nlogn)的时间复杂度之内找出任意一个极小值的位置，并输出它在第几行第几列。
本题中矩阵是隐藏的，你可以通过我们预设的int函数query来获得矩阵中某个位置的数值是多少。
例如，query(a,b)即可获得矩阵中第a行第b列的位置的数值。
注意：

矩阵的行和列均从0开始编号。
query()函数的调用次数不能超过(n+2)×?log2n?+n
答案不唯一，输出任意一个极小值的位置即可。

数据范围 1 ≤ n ≤ 300，矩阵中的整数在int范围内。
输入样例：

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

输出样例：

[0, 0]

思路 ? 这道题我们通过二分的思想解决，我们假设一个如下5 * 5的矩阵

12345 678910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

? 肉眼可见，我们直接就可以看出本矩阵的极小值是1，但是我们怎么实现合格问题呢？
? 我们先从中间列也就是第2列将矩阵分为两部分，左和右，之后我们从中间列从上到下第一个元素开始遍历中间列，找到中间列的最小值，可以看到，最小值是3，随后我们对比3的左右元素，如果这时3的左右元素都> 3，那很幸运，3就是矩阵的极小值，如果3的左右元素有< 3的，那么我们只需要再次二分这半部分矩阵即可，因为这半部分矩阵中，一定存在极小值
? 系统给我们提供了query(x, y)函数来获取矩阵中(x, y)位置的元素，但是有使用次数限制，这里的限制证明过程过于繁琐，我们只需要尽量降低query(x, y)函数的使用次数即可
? 最后经过不断二分操作，矩阵一定只剩下一列，这时我们只需要取这一列的最小值即可，这个值便是整个矩阵的极小值！代码如下：
代码

class Solution { public: vector getMinimumValue(int n) { long INF = 1e15; int l = 0, r = n - 1; int k; while (l < r) { int mid = (l + r) / 2; long min = INF; for (int i = 0; i < n; ++i) { int val = query(i, mid); if (min >= val) { min = val; k = i; } } long left = mid ? query(k, mid - 1) : INF; long right = (mid + 1) < n ? query(k, mid + 1) : INF; if (left > min && right > min) return{ k, mid }; if (left < min) r = mid - 1; else l = mid + 1; } long min = INF; for (int i = 0; i < n; i++) { int val = query(i, r); if (min > val) { min = val; k = i; } } return { k, r }; } };