一道在矩阵网格中寻找峰值的二分问题

来自 12 月 19 日 leetcode 的每日一题 1901. 寻找峰值 II,挺有趣的二分题, 关键在于如何证明。

问题描述:

一个 2D 网格中的「峰值」是指那些 严格大于 其相邻格子 (上、下、左、右) 的元素。

给定一个 m x n 的正整数矩阵 g,任意两个相邻方格的数字都不相同,找出任意一个峰值的位置。

可以假定整个矩阵周边环绕着一圈值为 -1 的格子,也就是说边缘的格子和界外相比总可以算做更大的值。

题目还提示了要用 $O(m\log{n})$ 或 $O(n\log{m})$ 时间复杂度的算法,强烈的二分法暗示。

比如说,下面的示例矩阵,可行解是绿色的任何一个方格 [1,1][2,2] 都可以。

虽然这个题「相邻元素互不相同」、「找到任意一个峰值」、「可以假定界外都是 -1」 的这些条件显得非常「刻意」, 但是单说解法而言,还是挺巧妙的。

总的思路是,二分枚举可行区间的行,然后找行内最大值进行判定

大概的伪代码如下,非常简洁:

int l = 0, r = m - 1;
while (l <= r) {
    int i = (l + r) >> 1;
    // 行内最值位置
    int j = max_element(g[i].begin(), g[i].end()) - g[i].begin();
    if (i >= 1 && g[i][j] <= g[i-1][j])
        r = i - 1;
    else if (i+1 < m && g[i][j] <= g[i+1][j])
        l = i + 1;
    else
        return {i, j};
}

关键是,这种二分方式如何是正确的呢

只说明第一个逻辑分支的情况,另一个分支道理类似。

首先,要时刻注意相邻元素不相等这个性质。

假设当前是第 i 行,行内的最大值是 A = g[i][j]

现在,遇到其上方的 B = g[i-1][j] 满足 A < B

假设 B 所在行的最大值是 C, 它下面相邻的是 D,那么肯定有 C >= B > A >= D,也就是 A > D

C 已经是行内最大了,只需要继续考虑 C 和其上面的 E 的大小关系。

如下图所示,红色的都是行内最值:


             E
        B    C
------- A -- D ----- i

分情况讨论:

  1. 如果 E < C, 那么 C 是一个可行解。
  2. 如果 E > C, 继续假设 E 所在行的最大值是 F,和刚才一样的推导方式可以知道 F > G (提示:C 是行内最大值,且此时假设的是 E > C)。

    此时,F 已经是行内最大,只需要再和它上方的数字进行比较,这样就形成了「套娃逻辑」。

    
                 E    F
            B    C    G
    ------  A -- D ----- i
    

    一旦走到第 1 种情况,就会得到一个可行解。

    如果不断陷入第 2 种情况,直到边缘第 1 行时会终止,因为题目假设边界外是 -1,即可以确定峰值。

综合来看,此时无论哪种情况,第 i 行的上方必有峰值,可把可行区间折半到 [l, i-1]

对于第二个逻辑分支的情况,不必再展开讨论。

(完)


相关阅读: 寻找峰值

本文原始链接地址: https://writings.sh/post/find-peak-in-grid

王超 ·
微信扫码赞赏
评论 首页 | 归档 | 算法 | 订阅