Maximum Number in Mountain Sequence

LeetCode LintCode

public class Solution {
    /**
     * @param nums a mountain sequence which increase firstly and then decrease
     * @return then mountain top
     */
//      Given nums = [1, 2, 4, 8, 6, 3] return 8
//      Given nums = [10, 9, 8, 7], return 10
//      last one which satisfy  i - (i-1) > 0
    public int mountainSequence(int[] nums) {
        // Write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while ( start + 1 < end) {
            int mid = start + ( end - start) /2 ;
            if ( (nums[mid + 1] - nums[mid]) < 0 ){
                end = mid;
            } else {
                start = mid;
            }
        }
        if (nums[start] - nums[end] > 0 ) {
            return nums[start];
        } else {
            return nums[end];
        }
    }
}

这一题用老师讲的二分法第二境界来处理会很方便。

老师举例说，该类题目是让你去找一组oooooxxxxx中的第一个x或者最后一个o。也就是给你一个数组，然后让你去找数组中第一个／最后一个满足某个条件的位置。

这里的Maximum Number in Mountain Sequence实际上是让我们找波峰。我们将问题简化为找数组中最后一个满足（ a[i] - a[i - 1] > 0)的a[i]，或者说最后一个导数大于零的数，或者最后一个保持递增的点； 也可以说是第一个满足（a[i+1] - a[i] < 0)的a[i].

先套用二分法模版, 决定判断标准为:

while (start + 1 < end) {
    if ( nums[mid + 1] - nums[mid] < 0 ) {
        end = mid;
    } else {
      start = end;
      }
}

循环结束后，有可能有三种情况：
- 只有一个元素
- 两个元素，递增
- 两个元素，递减

所以需要添上：

if (nums[start] - nums[end] > 0 ) {
            return nums[start];
        } else {
            return nums[end];
        }
}