高频面试题
思路是列二分,注意不能行列二分,行列二分得到的答案不一定正确。
// Forward declaration of queryAPI.
// int query(int x, int y);
// return int means matrix[x][y].
class Solution {
public:
vector<int> getMinimumValue(int n) {
const int INF = 1e9;
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r >> 1;
int k; //k用于储存最小值行数
int val = INF;
for (int i = 0; i < n; i ++ ) //遍历中间列元素
{
int t = query(i, mid); //从上至下查找mid列最小值
if (t < val)
{
val = t;
k = i; //最小值坐标为(k, mid)
}
}
//查看mid列最小值点的左右端点
int left = mid ? query(k, mid - 1) : INF; //如果已经是最左列,则不存在左端点
int right = mid + 1 < n ? query(k, mid + 1) : INF; //如果已经是最右列,则不存在右端点
if (val < left && val < right) return {k, mid}; //若当前值已经小于左右端点值,它已经是极小值
if (left < val) r = mid - 1; //往左靠
else l = mid + 1; //往右靠
}
//退出循环表示现在列二分到只剩下最后一列了,重复从上往下扫描的步骤即可
int k;
int val = INF;
for (int i = 0; i < n; i ++ )
{
int t = query(i, r);
if (t < val)
{
val = t;
k = i;
}
}
return {k, r}; //最后一列的最小值必定是极小值
}
};