算法面試真題詳解： 尋找峰值 II

描述

給定一個整數矩陣 A, 它有如下特性:

相鄰的整數不同

矩陣有 n 行 m 列，n和m不會小于3。

對于所有的 i < n, 都有 A[i][0] < A[i][1] && A[i][m - 2] > A[i][m - 1]

對于所有的 j < m, 都有 A[0][j] < A[1][j] && A[n - 2][j] > A[n - 1][j]

我們定義一個位置 [i,j] 是峰值, 當且僅當它滿足:

A[i][j] > A[i + 1][j] && A[i][j] > A[i - 1][j] &&

A[i][j] > A[i][j + 1] && A[i][j] > A[i][j - 1]

找到該矩陣的一個峰值元素, 傳回它的坐标.

保證至少存在一個峰值, 而如果存在多個峰值, 傳回任意一個即可.

線上評測位址：

領扣題庫官網

樣例 1:
輸入: 
    [
      [1, 2, 3, 6,  5],
      [16,41,23,22, 6],
      [15,17,24,21, 7],
      [14,18,19,20,10],
      [13,14,11,10, 9]
    ]
輸出: [1,1]
解釋: [2,2] 也是可以的. [1,1] 的元素是 41, 大于它四周的每一個元素 (2, 16, 23, 17).           

樣例2：
輸入: 
    [
      [1, 5, 3],
      [4,10, 9],
      [2, 8, 7]
    ]
輸出: [1,1]
解釋: 隻有這一個峰值           

挑戰

O(n+m) 的時間複雜度.

如果你 認為 你使用了 O(nlogm) 或 O(mlogn) 的算法, 能否證明它的複雜度其實是 O(n+m)? 或者想一個類似的算法但是複雜度是O(n+m)？

解題思路

峰值不是最大值，隻是比四個方向上的數值都大，是局部性的最值。

對于每一個點，它總能屬于某一座山峰（可以不止一座）。

找峰值可以想象成爬山，總是要不斷的從低處向高處移動，這樣移動到最後一定是峰值。

代碼思路

在圖上随機取一點，若有相鄰位置比目前點大則向該相鄰位置移動，直到目前點成為峰值。

最壞情況是螺旋式上升，且随機在了起點位置，那麼就要爬升一半的點

1 2 3 4 5

0 0 0 0 6

15 16 17 0 7

14 0 0 0 8

13 12 11 10 9

如果遇到最壞的情況，我們可以通過當爬升超過一定距離後重新随機一個點，使得相對平均效率較高

複雜度分析

NN表示行數，MM表示列數

空間複雜度：O(1)

平均時間複雜度：O(N+M)

public class Solution {

    /*

     * @param A: An integer matrix

     * @return: The index of the peak

     */

    public List<Integer> findPeakII(int[][] A) {

        int n = A.length;

        int m = A[0].length;

        int now_x, now_y, next_x, next_y;

        //這裡初始位置選擇為中心位置

        now_x = n / 2;

        now_y = m / 2;

        while (1 == 1) {

            next_x = now_x;

            next_y = now_y;

            //四個方向上若有比目前位置大的，則向該方向移動

            if (now_x + 1 < n && A[now_x + 1][now_y] > A[next_x][next_y]) {

                next_x = now_x + 1;

                next_y = now_y;

            }else if (now_x - 1 >= 0 && A[now_x - 1][now_y] > A[next_x][next_y]) {

                next_x = now_x - 1;

                next_y = now_y;

            }else if (now_y + 1 < m && A[now_x][now_y + 1] > A[next_x][next_y]) {

                next_x = now_x;

                next_y = now_y + 1;

            }else if (now_y-1 >= 0 && A[now_x][now_y - 1] > A[next_x][next_y]) {

                next_x = now_x;

                next_y = now_y - 1;

            }

            //若四個方向上都比目前位置小，即為峰值直接傳回答案

            if (next_x == now_x && next_y == now_y) {

                return new ArrayList<Integer>(Arrays.asList(now_x, now_y));

            }

            now_x = next_x;

            now_y = next_y;

        }

    }

}           

更多題解參考：

九章官網solution