山峰数组三题

845. 数组中的最长山脉

     
     845. 数组中的最长山脉

解题思路： 就是用动态规划，计算所有元素，左边的元素数量，右边的元素数量，最终山脉长度为并且山脉的长度为left[i] + right[i] + 1

领扣题解

class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int[] left =  new int[n];
        for (int i = 1; i < n ; i++) {
            left[i] = arr[i] > arr[i-1] ? left[i-1] + 1 : 0;
        }

        int[] right = new int[n];
        for (int i = n - 2; i > 0 ; i--) {
            right[i] = arr[i] > arr[i+1] ? right[i+1] + 1 : 0;
        }
        int ans = 0;
        for(int i = 1; i < n - 1; ++i) {
            if (left[i] > 0 && right[i] > 0) {
                ans = Math.max(ans,left[i] + right[i] + 1);
            }
        }
        return ans;
    }
}

山脉数组索引

解题思路：二分查找

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int l0 = 0, hi = arr.length - 1;
        while (l0 < hi) {
            int mi = l0 + (hi - l0) / 2 ;
            if (arr[mi] < arr[mi+1]) {
                l0 = mi + 1;
            } else {
                hi = mi;
            }
        }
        return l0;
    }
}

有效的山峰数组 有效的山峰数组

解题思路：很简单，顺序遍历出最大的，反过来继续遍历，注意边界条件

class Solution {
    public boolean validMountainArray(int[] arr) {
        int N = arr.length;
        int i = 0;

        // 递增扫描
        while (i + 1 < N && arr[i] < arr[i + 1]) {
            i++;
        }

        // 最高点不能是数组的第一个位置或最后一个位置
        if (i == 0 || i == N - 1) {
            return false;
        }

        // 递减扫描
        while (i + 1 < N && arr[i] > arr[i + 1]) {
            i++;
        }

        return i == N - 1;
    }
}