题解 | #寻找峰值#

寻找峰值

http://www.nowcoder.com/practice/1af528f68adc4c20bf5d1456eddb080a

题目描述

山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。

假设 nums[-1] = nums[n] = -∞。

大体思路

题目中的山峰元素定义是要大于等于其紧邻的左右两边的元素就行了，紧接着又说传入的数组中相邻的两个元素值是不相等，所以很自然的就会想到遍历的方式。可以从左往右遍历，也可以从右往左遍历。

因为题目所要求的是索引最大的山峰元素的峰值的，所以从左往右的遍历方式中，我们不能找到一个峰值就停止，要一直往右找完所有山峰元素；但是在从右往左的遍历方式中，我们只要找到第一个山峰元素，就可以停止遍历了，因为第一个找到的山峰元素，就是索引值最大的山峰元素，再往左边找，那索引值只能越来越小。

方法一：从左往右遍历

解题思路

为了防止数组下标越界的问题，就只看数组中第 2 个数字到倒数第 2 个数字这个范围就好了，在遍历的过程要和其左右两边的元素都做比较。先让山峰元素初始化为第 1 个数字，最后再来单独看看最后一个数字是不是山峰元素。

整个过程就很简单很暴力，具体的相关流程见下图示和代码示例。
图片说明

代码示例

import java.util.*;


public class Solution {
    /**
     * 寻找最后的山峰 
     */
    public int solve (int[] nums) {
        // 判断特殊情况
        if (nums == null || nums.length == 0) {
            return -1;
        }

        // 只有一个数字，那他自己就是峰值
        if (nums.length == 1) {
            return 0;
        }

        // 最大的索引
        int maxIndex = 0;

        // 从第2个数字开始往后遍历到倒数第二个数字
        for (int i = 1; i < nums.length - 1; i++) {
            // 只要比前一个数字、后一个数字都大， 那就是峰值
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                maxIndex = i;
            }
        }

        // 判断最后一个索引是不是最大峰值
        if (nums[nums.length - 1] > nums[nums.length - 2]) {
            maxIndex = nums.length - 1;
        }

        return maxIndex;
    }
}

复杂度分析

时间复杂度：O(N)

整个过程就是从第 2 个数字到倒数第 2 个数字遍历了一遍，只剩 2 个数字在循环里没有遍历到，但但对于 N 这个的变量来说，2 个数字这样的常量所带来的性能消耗可以忽略不计了。所以，总的时间复杂度即为 O(N)。

空间复杂度：O(1)

整个代码中没有出现子再开辟新空间的地方，只有一个用来记录山峰元素当中的最大索引值的整型变量。所以，空间复杂度为 O(1)。

方法二：从右到左遍历

解题思路

在从右往左的遍历过程中，为了防止下标越界，所以遍历顺序及遍历范围就是从右往左遍历最后一个数字到第 2 个数字。在遍历的过程中，只要看是否比他前面的那个数字大就好了，找到了就更新山峰元素的最大索引值，然后退出循环。

因为最后一个数字的右边没有数字，如果在这个过程中找到了一个比他前面那个数字大的元素，那他必定是山峰元素，因为他也比他右边的那个数字大，如果他没有比他右边的那个数字大，那他根本就来不到这一步，因为他右边的那个数字也是一个山峰元素，且索引值要比他的还要大。

在遍历之前，先对山峰元素的最大索引值初始化为 0 ，代表第 1 个数字就是山峰元素，如果在从右到左遍历的过程中，没有找到山峰元素，那么说明第 1 个数字是山峰元素，且是索引值最大的山峰元素。

简单的说，题目要求的是索引最大的山峰元素，所以，可以直接从后往前遍历，只要找到第一个山峰元素，他的索引值就是我们要找的答案。

整个过程可见下图及代码示例：
图片说明

代码示例

import java.util.*;


public class Solution {
    /**
     * 寻找最后的山峰 
     */
    public int solve (int[] nums) {
        // 判断特殊情况
        if (nums == null || nums.length == 0) {
            return -1;
        }

        // 数组只有1个数字，那他自己就是峰值
        if (nums.length == 1) {
            return 0;
        }

        // 最大的索引
        int maxIndex = 0;

        // 从后往前遍历
        for (int i = nums.length - 1; i > 0; i--) {
            // 只要比前面的数大，就是峰值
            if (nums[i] > nums[i - 1]) {
                maxIndex = i;
                break;
            }
        }

        return maxIndex;
    }
}