Leetcode.162.Find Peak Element

题目

给定一个数组, 找到一个数比相邻的数都要大, 假设 nums[-1] = nums[n] = -∞, 输出数的索引.

Input: [1,2,3,1]
Output: 2
Input: [1,2,1,3,5,6,4]
Output: 1 or 5

思路

就是简单的循环, 注意边界条件.

int findPeakElement(vector<int>& nums) {
    int n = (int)nums.size();
    if (n <= 1) {
        return 0;
    } else if (nums[0] > nums[1]) {
        return 0;
    } else if (nums[n-1] > nums[n-2]) {
        return n-1;
    }

    for(int i = 1;i < nums.size()-1;) {
        if (nums[i-1] > nums[i]) {
            i += 2;
        } else if (nums[i+1] > nums[i]) {
            i +=1;
        } else {
            return i;
        }
    }
    return 0;
}

总结

尽量去优化, 降低时间和空间复杂度.