Leetcode 845. 数组中的最长山脉 C++

Leetcode 845. 数组中的最长山脉

题目

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：

• B.length >= 3
• 存在 0 < i < B.length - 1 使得 B[0] < B[1] < … B[i-1] B[i+1] > … > B[B.length - 1]

（注意：B 可以是 A 的任意子数组，包括整个数组 A。）

给出一个整数数组 A，返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

测试样例

示例 1：

输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。

示例 2：

输入：[2,2,2]
输出：0
解释：不含 “山脉”。

提示：

1. 0 <= A.length <= 10000
2. 0 <= A[i] <= 10000

题解

遍历所有的山顶，然后找取最长的山脉。详细过程见代码

代码

	int longestMountain(vector<int>& A) {int maxLength = 0;int n = A.size(),i=0;while(i < n){int j = i+1;while(j<n && A[j]>A[j-1])   j++;		//找到山顶if(j == i+1)    i++;	//不是山顶else{	//左边符合山顶，找右边界int k=j;while(k<n && A[k]<A[k-1]) k++;if(k == j)    i = k;		//右边不符合山顶要求else{		//是山顶，取长度最大maxLength = max(maxLength,k-i);i = k-1;}    }}return maxLength;}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-mountain-in-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！