Peak Finding
peak(数学里的极大点,不过数组是离散的)
###1.一维情况
peak定义
对一维数组一般元素而言如果当前元素比左右的元素都不小(>=),它就是极点
而起点和终点只要比它旁边的元素大就是极点了
这样的定义下数组至少有一个极点
解法
1.遍历一遍,找到peak
时间复杂度: O(n)
2.分治法
查看n/2元素是否是极点,不是的话,沿着元素较大的方向继续查找
时间复杂度: O(log(n))
###2.二维情况
peak定义
对二维的数组而言,当前元素比上下左右四个元素都不小
####解法
1.贪心算法
按一定顺序比较和四个方向上元素的大小,朝较大的方向移动,直到找到极点
时间复杂度: O(mn)
2.分治法
对于j=m/2 找到该列最大点,按顺序比较左右元素,沿着较大值的方向递归