2023-12-19每日一題

一、題目編號

1901. 尋找峰值 II

二、題目鏈接

點擊跳轉(zhuǎn)到題目位置

三、題目描述

一個 2D 網(wǎng)格中的 峰值 是指那些 嚴(yán)格大于 其相鄰格子(上、下、左、右)的元素。

給你一個 從 0 開始編號 的 m x n 矩陣 mat ，其中任意兩個相鄰格子的值都 不相同 。找出 任意一個 峰值 mat[i][j] 并 返回其位置 [i,j] 。

你可以假設(shè)整個矩陣周邊環(huán)繞著一圈值為 -1 的格子。

要求必須寫出時間復(fù)雜度為 O(m log(n)) 或 O(n log(m)) 的算法

示例 1:

示例 2:

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 10⁵
• 任意兩個相鄰元素均不相等.

四、解題代碼

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 >= 0 && mat[i][j] < mat[i - 1][j]) {high = i - 1;continue;}if (i + 1 < m && mat[i][j] < mat[i + 1][j]) {low = i + 1;continue;}return {i, j};}return {}; // impossible}
};

五、解題思路

(1) 二分查找。