585.Maximum Number in Mountain Sequence

1.Description(Medium)

Given a mountain sequence ofnintegers which increase firstly and then decrease, find the mountain top.

Example

Givennums=[1, 2, 4, 8, 6, 3]return8 Givennums=[10, 9, 8, 7], return10

2.Code

这道题用的是三分，而不是二分 三分是用两个mid的 二分处理的是，连续上升或连续下降的问题 三分处理的是，连续上升接连续下降的问题

二分处理的是有序的问题，如递增，或者递减

三分解决的是极值问题，也就是凸函数，如 y = x^2, 求最小值，你可以在[-oo, oo]区间内三分

public int mountainSequence(int[] nums) {
        if(nums==null || nums.length==0){
            return -1;
        }
        int left=0;
        int right=nums.length-1;
        while(left+1<right){
            int mid1=left+(right-left)/2;
            int mid2=right-(right-mid1)/2;
            if(nums[mid1]<nums[mid2]){
                left=mid1+1;
            }else if(nums[mid1]>nums[mid2]){
                right=mid2-1;
            }else{
                left=mid1;
                right=mid2;
            }
        }
        return nums[left]>nums[right]?nums[left]:nums[right];

    }