AcWing 1452. 寻找矩阵的极小值
宋标 Lv5
  2022-08-18 02:31:52 2022-08-18 02:31    

题目

给定一个 的矩阵，矩阵中包含 个 互不相同 的整数。

定义极小值：如果一个数的值比与它相邻的所有数字的值都小，则这个数值就被称为极小值。

一个数的相邻数字是指其上下左右四个方向相邻的四个数字，另外注意，处于边界或角落的数的相邻数字可能少于四个。

要求在 的时间复杂度之内找出任意一个极小值的位置，并输出它在第几行第几列。

本题中矩阵是隐藏的，你可以通过我们预设的 函数 来获得矩阵中某个位置的数值是多少。

例如， 即可获得矩阵中第 行第 列的位置的数值。

注意：

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

数据范围

，矩阵中的整数在int范围内。

输入样例：

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

输出样例：

[0, 0]

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Forward declaration of queryAPI.
// int query(int x, int y);
// return int means matrix[x][y].

class Solution {
public:
    vector<int> getMinimumValue(int n) {
        typedef long long LL;
        const LL INF = 1e15;
        int l = 0, r = n - 1;
        while (l <= r)
        {
            int mid = l + r >> 1;
            //取列最小值
            LL y, k = INF;
            for (int i = 0; i < n; ++ i)
            {
                int t = query(i, mid);
                if (k > t) k = t, y = i;
            }

            if (l == r) return {y, l};

            //判断边界
            LL left = mid ? query(y, mid - 1) : INF;
            LL right = mid < n - 1 ? query(y, mid + 1) : INF;

            if (k < left && k < right) return {y, mid};
            if (k > left) r = mid - 1;
            else l = mid + 1;
        }
        return {-1, -1};
    }
}
 评论