山脉数组中查找目标值

题目描述

https://leetcode-cn.com/problems/find-in-mountain-array/

解

// 找到峰顶
// 在峰顶左边 递增数组
// 在峰顶右边 递减数组
func findPeakSlope(pStart, pEnd int, pMountainArr *MountainArray) int {
    for pStart < pEnd {
        mid := pStart + (pEnd-pStart)/2
        midNum := pMountainArr.get(mid)
        if pMountainArr.get(mid+1) > midNum {
            pStart = mid + 1
        } else {
            pEnd = mid
        }
    }
    return pStart
}

// 递增排序
func FindPositiveSlope(pStart, pEnd, pTarget int, pMountainArr *MountainArray) int {
    mid := (pStart + pEnd) / 2
    for pStart <= pEnd {
        if pMountainArr.get(mid) == pTarget {
            return mid
        }
        if pMountainArr.get(mid) > pTarget {
            pEnd = mid - 1
        } else {
            pStart = mid + 1
        }
        mid = (pStart + pEnd) / 2
    }
    return -1
}

// 递减排序
func FindBackSlope(pStart, pEnd, pTarget int, pMountainArr *MountainArray) int {
    mid := (pStart + pEnd) / 2
    for pStart <= pEnd {
        if pMountainArr.get(mid) == pTarget {
            return mid
        }
        if pMountainArr.get(mid) > pTarget {
            pStart = mid + 1
        } else {
            pEnd = mid - 1
        }
        mid = (pStart + pEnd) / 2
    }
    return -1
}
func findInMountainArray(target int, mountainArr *MountainArray) int {
    // 错误处理
    if mountainArr.length() == 0 {
        return -1
    }
    // 二分查找
    peakIndex := findPeakSlope(0, mountainArr.length()-1, mountainArr)
    if mountainArr.get(peakIndex) == target {
        return peakIndex
    }
    // 递增
    r := FindPositiveSlope(0, peakIndex-1, target, mountainArr)
    if r != -1 {
        return r
    }
    r = FindBackSlope(peakIndex+1, mountainArr.length()-1, target, mountainArr)
    return r
}

思路

题目的关键点是山脉数组，山脉的特点是：顶峰向左是递增的；顶峰向右是递减的利用这个特性，首先找出顶峰节点，在往两边的递增递减数据使用二分就能轻易的解了，虽然是hard模式，但是申清题目就很简单了！上面写了很多多余的代码，这个大家见笑了！