Find Peek Element II

There is an integer matrix which has the following features:

The numbers in adjacent positions are different. The matrix has n rows and m columns. For all i < m, A[0][i] < A[1][i] && A[n - 2][i] > A[n - 1][i]. For all j < n, A[j][0] < A[j][1] && A[j][m - 2] > A[j][m - 1]. We define a position P is a peek if:

A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1] Find a peak element in this matrix. Return the index of the peak.

先找到某列最大元素，再二分 O(n lgm)

由于对每次都是查找某列所有元素，所以复杂度是O(nlgm)

class Solution {
public:
    /**
     * @param A: An integer matrix
     * @return: The index of the peak
     */
    vector<int> findPeakII(vector<vector<int> > A) {
        // write your code here
        if(A.size()<=2)return vector<int>();

        int tlC=1,brC=A[0].size()-2;

        while(tlC<=brC)
        {
            int midC=(tlC+brC)>>1;
            int maxH=findMaxInCol(A,midC,0,A.size()-1);

            if(A[maxH][midC]<A[maxH][midC+1])tlC=midC+1;
            else if(A[maxH][midC]<A[maxH][midC-1])brC=midC-1;
            else
            {
                vector<int> ret;
                ret.push_back(maxH);
                ret.push_back(midC);
                return ret;
            }
        }
        return vector<int>();
    }

    int findMaxInCol(vector<vector<int> > &A,int col,int th,int bh)
    {
        int maxh=th;

        for(int hi=th;hi<=bh;hi++)
        {
            if(A[maxh][col]<A[hi][col])maxh=hi;
        }

        return maxh;
    }
};

每次排除一半，复杂度O(n+m)

详情参考这里。虽然提到了一个pdf证明复杂度，但是这个pdf看着好累，没完全理解。

class Solution {
public:
    /**
     * @param A: An integer matrix
     * @return: The index of the peak
     */
    vector<int> findPeakII(vector<vector<int> > A) {
        // write your code here
        if(A.size()<=2)return vector<int>();

        int up=0,down=A.size()-1;
        int left=0,right=A[0].size()-1;

        while(up<=down && left<=right)
        {
            int midH=(up+down)>>1;

            //找到某一行中最大的那一列
            int maxw=findMaxInRow(A,midH,left,right);

            //排除上半部分
            if(A[midH][maxw]<A[midH+1][maxw])up=midH+1;
            //排除下半部分
            else if(A[midH][maxw]<A[midH][maxw-1])down=midH-1;
            else
            {
                return {midH,maxw};
            }

            int midC=(left+right)>>1;

            //找到某一列中最大的行
            int maxH=findMaxInCol(A,midC,up,down);

            //排除左边
            if(A[maxH][midC]<A[maxH][midC+1])left=midC+1;
            else if(A[maxH][midC]<A[maxH][midC-1])right=midC-1;
            else
            {
                return {maxH,midC};
            }
        }
        return vector<int>();
    }

    int findMaxInCol(vector<vector<int> > &A,int col,int up,int down)
    {
        int maxh=up;

        for(int hi=up;hi<=down;hi++)
        {
            if(A[maxh][col]<A[hi][col])maxh=hi;
        }

        return maxh;
    }
    int findMaxInRow(vector<vector<int> > &A,int row,int left,int right)
    {
        int maxw=left;

        for(int wi=left+1;wi<=right;wi++)
        {
            if(A[row][maxw]<A[row][wi])maxw=wi;
        }

        return maxw;
    }
};

O(n+m) 从左上角往右下挪动

这个算法真的是我看到最简洁的算法了！

class Solution {
public:
    /**
     * @param A: An integer matrix
     * @return: The index of the peak
     */
    vector<int> findPeakII(vector<vector<int> > A) {
        // write your code here

        if(A.size()<=2)return vector<int>();
        int h=1,w=1;
        while(h<A.size()-1 && w<A[0].size()-1)
        {
            if(A[h][w]>A[h][w+1]&& A[h][w]>A[h+1][w])
            return {h,w};
            else if(A[h][w+1]>A[h+1][w])
            {
                w++;
            }
            else h++;
        }

        return vector<int>();
    }
};