本文主要是介绍LeetCode 每日一题 845.数组中的最长山脉,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
10.25
LeetCode 每日一题 845.数组中的最长山脉
方法一:从山顶进行枚举
思路分析:
题目所要求的山脉的形式就是相当于“金字塔型”,山顶的左边和右边都依次变低,但是这个金字塔并不是左右对称的,只需要保证山顶的左边和右边依次递减即可。所以我们可以从山顶出发,求出以每一个点为山顶,能够组成的最长山脉,最后返回这个最长山脉的长度即可。
假设给出的数组长度为len
,这个时候,因为山顶不能没有左边和右边,所以山顶从1
开始枚举,枚举到len-1
。这样子求出每一个山脉的长度。因为左边和右边都必须满足依次递减这个条件,所以我们可以创建两个数组分别储存某个山顶左边和右边的最长长度。
算法分析:
创建 left
数组,right
数组,假设当前以i
为山顶,此时left[i]
则表示山脉左边的长度,right[i]
表示山脉右边的长度。当A[i-1]<A[i]
时,则证明此时满足递减,所以left[i]=left[i-1]+1
。(为什么要这样做呢?因为left[0]
肯定是为0
的,这里就利用了动态规划的思想,每一个left
数组都存放了以i
为顶点,左边的最长递减子串的长度)!
此时如果left[i]
和right[i]
都大于0
,则证明以i
为山顶可以组成山脉,组成山脉的长度则为 left[i]+right[i]+1
。
上面步骤储存了每个顶底组成的最长山脉的长度(不能组成的也归在里面,则长度为0),最后遍历所有可能的顶点,比较取得山脉的最长长度
maxLen = Math.max(maxLen,left[i]+right[i]+1)
。
下面贴出代码:
public int longestMountain(int[] A) {int len = A.length;if (len == 0)return 0;int[] left = new int[len];for
这篇关于LeetCode 每日一题 845.数组中的最长山脉的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!