Find Peak Element 2

思路

http://www.lintcode.com/en/problem/find-peak-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]

code

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
        vector<int> ret;
        int m = A.size();
        if(m == 0)
        {
            return ret;
        }
        int n = A[0].size();

        return helper(A, 0, m-1, 0, n-1);
    }

    vector<int> helper(vector<vector<int>>& A, int sm, int em, int sn, int en)
    {
        vector<int> ret;
        if(sm >= em || sn >= en)
        {
            return ret;
        }

        int midm = (sm + em)/2;
        int maxnindex = findIndexOfMaxValue(A, midm, midm, sn, en);

        if(checkValid(A, midm, maxnindex))
        {
            ret.push_back(midm);
            ret.push_back(maxnindex);
            return ret;
        }

        if(A[midm][maxnindex] < A[midm-1][maxnindex])
        {
            em = midm;
        }
        else
        {
            sm = midm;
        }

        int maxmindex = findIndexOfMaxValue(A, sm, em, maxnindex, maxnindex);
        if(checkValid(A, maxmindex, maxnindex))
        {
            ret.push_back(maxmindex);
            ret.push_back(maxnindex);
            return ret;
        }

        if(A[maxmindex][maxnindex] < A[maxmindex][maxnindex-1])
        {
            return helper(A, sm, em, sn, maxnindex);
        }
        else
        {
            return helper(A, sm, em, maxnindex, en);
        }

    }

    bool checkValid(vector<vector<int>>& A, int x, int y)
    {
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};

        int cur = A[x][y];

        for(int i = 0; i<4; i++)
        {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(cur < A[nx][ny])
            {
                return false;
            }
        }
        return true;
    }

    int findIndexOfMaxValue(vector<vector<int>>& A, int sm, int em, int sn, int en)
    {
        if(sm == em)
        {
            int maxvalue = A[sm][sn];
            int maxindex = sn;
            for(int i = sn; i <= en; i++)
            {
                if(A[sm][i] > maxvalue)
                {
                    maxvalue = A[sm][i];
                    maxindex = i;
                }
            }

            return maxindex;
        }

        if(sn == en)
        {
            int maxvalue = A[sm][sn];
            int maxindex = sm;
            for(int i = sm; i <= em; i++)
            {
                if(A[i][sn] > maxvalue)
                {
                    maxvalue = A[i][sn];
                    maxindex = i;
                }
            }

            return maxindex;
        }

        return -1;
    }
};