1901. 寻找峰值 II

1901. 寻找峰值 II

• 难度: medium
• 原始链接: https://leetcode.cn/problems/find-a-peak-element-ii
• 标签: 二分查找

解法一: 暴力

go

func findPeakGrid(mat [][]int) []int {
    m := len(mat)
    n := len(mat[0])
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if (r == 0 || mat[r][c] > mat[r - 1][c]) &&
                (r == m - 1 || mat[r][c] > mat[r + 1][c]) &&
                (c == 0 || mat[r][c] > mat[r][c - 1]) &&
                (c == n - 1 || mat[r][c] > mat[r][c + 1]) {
                return []int{r, c}
            }    
        }
    }
    return []int{}
}

解法二: 二分查找

go

func findPeakGrid(mat [][]int) []int {
    m := len(mat)
    left := 0
    right := m - 1
    for left < right {
        mid := ((right - left) >> 1) + left
        i := maxIndex(mat[mid])
        if mat[mid][i] < mat[mid + 1][i] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return []int{left, maxIndex(mat[left])}
}

func maxIndex(nums []int) int {
    ans := 0
    for i, num := range nums {
        if nums[ans] < num {
            ans = i
        }
    }
    return ans
}