美文网首页
845. 数组中的最长山脉

845. 数组中的最长山脉

作者: 程序员小2 | 来源:发表于2022-10-22 11:22 被阅读0次

    题目:

    把符合下列属性的数组 arr 称为 山脉数组 :

    arr.length >= 3
    存在下标 i(0 < i < arr.length - 1),满足
    arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
    给出一个整数数组 arr,返回最长山脉子数组的长度。如果不存在山脉子数组,返回 0 。

    示例 1:

    输入:arr = [2,1,4,7,3,2,5]
    输出:5
    解释:最长的山脉子数组是 [1,4,7,3,2],长度为 5。
    示例 2:

    输入:arr = [2,2,2]
    输出:0
    解释:不存在山脉子数组。

    提示:

    1 <= arr.length <= 104
    0 <= arr[i] <= 104

    进阶:

    你可以仅用一趟扫描解决此问题吗?
    你可以用 O(1) 空间解决此问题吗?

    思路:

    枚举山顶
    我们可以考虑枚举山顶,再从山顶向左右两侧扩展找到山脚。

    由于从左侧山脚到山顶的序列是严格单调递增的,而从山顶到右侧山脚的序列是严格单调递减的,因此我们可以使用动态规划(也可以理解为递推)的方法,计算出从任意一个元素开始,向左右两侧最多可以扩展的元素数目。

    我们用left[i] 表示arr[i] 向左侧最多可以扩展的元素数目。如果arr[i−1]<arr[i],那么arr[i] 可以向左扩展到 arr[i−1],再扩展left[i] 个元素,因此有
    left[i]=left[i−1]+1

    如果 arr[i−1]≥arr[i],那么arr[i] 无法向左扩展,因此有
    left[i]=0

    特别地,当 i=0 时,arr[i] 为首元素,无法向左扩展,因此同样有
    left[0]=0

    同理,我们用 right[i] 表示arr[i] 向右侧最多可以扩展的元素数目,那么有类似的状态转移方程(递推式)
    right[i]=right[i+1]+1, (arr[i]>arr[i+1])
    right[i]=0, (arr[i]<=arr[i+1])

    在计算出所有的left 以及right 之后,我们就可以枚举山顶。需要注意的是,只有当left[i] 和 right[i] 均大于 00 时,arr[i] 才能作为山顶,并且山脉的长度为left[i]+right[i]+1。

    java代码:

    class Solution {
        public int longestMountain(int[] arr) {
            int n = arr.length;
            if (n < 3) {
                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 + 1] < arr[i] ? 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(left[i] + right[i] + 1, ans);
                }
            }
            return ans;
        }
    }
    

    相关文章

      网友评论

          本文标题:845. 数组中的最长山脉

          本文链接:https://www.haomeiwen.com/subject/oiwvzrtx.html