845. Longest Mountain in Array

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

You may recall that an array arr is a mountain array if and only if:

arr.length >= 3 There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that: arr[0] < arr[1] < … < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > … > arr[arr.length - 1] Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

Example 1:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

Code

DP

class Solution {
    public int longestMountain(int[] arr) {
        int res = 0, up = 0, down = 0, n = arr.length;

        for (int i = 1; i < n; i++) {
            // 从递减变成递增,重新开始计数
            if ((down != 0 && arr[i] > arr[i - 1]) || (arr[i - 1] == arr[i])) {
                up = down = 0;
            }

            // 递增数列
            if (arr[i] > arr[i - 1]) {
                up++;
            }
            // 递减数列
            if (arr[i] < arr[i - 1]) {
                down++;
            }

            if (up > 0 && down > 0) {
                res = Math.max(res, up + down + 1);
            }
        }

        return res;
    }
}

class Solution {
    public int longestMountain(int[] arr) {
        int[] up = new int[arr.length];
        int[] down = new int[arr.length];

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                up[i] = up[i - 1] + 1;
            }
        }

        int res = 0;
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                down[i] = down[i + 1] + 1;
            }

            if (up[i] != 0 && down[i] != 0) {
                res = Math.max(res, up[i] + down[i] + 1);
            }
        }

        return res;
    }
}