【每日一题】寻找峰值 II

Tag

【二分查找】【数组】【2023-12-19】

---

题目来源

1901. 寻找峰值 II

---

解题思路

方法一：二分查找

思路

类似于昨天的【每日一题】，解决本题之前需要先了解昨天的题目。

我们在行上进行二分搜索，在当前行的列中找出最大的值即可。具体地：

• 初始化 low = 0，high = mat.size() - 1；
• 当 low <= high 时，中点记为 i，i 行的最大值记为 mat[i][j]：
  • 如果 mat[i][j] < mat[i +1][j]，则更新 low = i + 1;
  • 如果 mat[i][j] < mat[i - 1][j]，则更新 high = i - 1。

算法

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int m = mat.size();
        int low = 0, high = m-1;
        while (low <= high) {
            int i = (low + high) / 2;
            int j = max_element(mat[i].begin(), mat[i].end()) - mat[i].begin();
            if (i + 1 < m && mat[i][j] < mat[i+1][j]) {
                low = i + 1;
                continue;
            }
            if (i - 1 >= 0 && mat[i][j] < mat[i-1][j]) {
                high = i - 1;
                continue;
            }
            return {i, j};
        }
        return {};
    }
};

复杂度分析

时间复杂度：$O(nlogm)$，$m$ 和 $n$ 分别为矩阵的行数和列数。

空间复杂度：$O(1)$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。