首页 > 编程语言 > 详细

LeetCode 845. 数组中的最长山脉

时间:2020-10-25 11:01:44      阅读:41      评论:0      收藏:0      [点我收藏+]

题目链接

845. 数组中的最长山脉 Medium

题目分析

这个题的难度纯粹就是吓唬人的。。这个题的思路有很多,可以先找山峰,然后再向左右扩展。我的想法就是在遍历过程中去维护一个双指针,双指针的距离就是当前山脉的长度。
遍历过程中分以下几种情况

  • 如果A[i] > A[i-1],那么这里可以看做山脉的起点,同时设置一个标志位flag来标记
  • 如果A[i] < A[i-1],那么这里可以看做山脉的下坡,我们内部再使用一个循环去寻找山脉的结束点。在寻找结束后,通过判断flag && fast - slow >= 3的条件,来进行res的计算。
  • 如果A[i] == A[i-1],这里没啥好说的,相同的元素,直接重置slowflag,然后让fast指向下一个元素即可。

代码实现

class Solution {
    public int longestMountain(int[] A) {
        int res = 0;
        int fast = 1;
        int slow = 0;
        boolean flag = false;
        while(fast < A.length){
            if(A[fast] > A[fast - 1]){
                fast++;
                flag = true;
            }else if(A[fast] < A[fast - 1]){
                while(fast < A.length && A[fast] < A[fast - 1]){
                    fast++;
                }
                if(flag && fast - slow >= 3){
                    res = Math.max(res, fast - slow);
                }
                slow = fast - 1;
                flag = false;
            }else{
                slow = fast;
                fast++;
                flag = false;
            }
        }
        return res;
    }
}

总结

有时候不要被题目的难度吓到自己了。
技术分享图片

LeetCode 845. 数组中的最长山脉

原文:https://www.cnblogs.com/ZJPaang/p/13872305.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!