首页 > 其他 > 详细

LintCode "Find Peak Element II"

时间:2015-10-06 08:03:35      阅读:236      评论:0      收藏:0      [点我收藏+]

Idea is the same: climbing up the hill along one edge (Greedy)! Visualize it in your mind!

class Solution {
public:
    /**
     * @param A: An integer matrix
     * @return: The index of the peak
     */
    vector<int> findPeakII(vector<vector<int> > A) 
    {
        int n = A.size();
        int m = A[0].size();
        
        int i = 1, j = 1;
        while(i < m - 1 && j < n - 1)
        {
            bool up   = A[j - 1][i] < A[j][i];
            bool down = A[j + 1][i] < A[j][i];
            bool left = A[j][i - 1] < A[j][i];
            bool right= A[j][i + 1] < A[j][i];
            
            if(up && down && left && right)
            {
                return {j, i};
            }
            if(!down && j < n - 2)
            {
                j ++;
            }
            else if(!right && i < m - 2)
            {
                i ++;
            }
        }
        
        return {-1, -1};
    }
};

LintCode "Find Peak Element II"

原文:http://www.cnblogs.com/tonix/p/4856654.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!