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

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

B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-mountain-in-array

——题目难度：中等



 

解题代码1
通过枚举 left 和 right 以及 山顶位置

class Solution {
public:int longestMountain(vector& A) {int n = A.size();if (n < 3) {return 0;}vector left(n, 0); //left[i] = x，表示A[i]向左侧最多可以扩展的元素的数目for(int i = 1; i < n; i++) left[i] = (A[i] > A[i-1] ? left[i-1] + 1 : 0);vector right(n, 0); //right[i] = x，表示A[i]向右侧最多可以扩展的元素的数目for(int i = n-2; i >= 0; i--) right[i] = (A[i] > A[i+1] ? right[i+1] + 1 : 0);int ans = 0;for(int i = 1; i < n - 1; i++) { //枚举山顶if (left[i] > 0 && right[i] > 0) ans = max(ans, left[i] + right[i] + 1); }return ans;}
};

双指针解法

class Solution {
public:int longestMountain(vector& A) {int n = A.size();int ans = 0;int left = 0;while (left + 2 < n) {int right = left + 1;if (A[left] < A[left+1]) { //找到左山脚 while (right < n - 1 && A[right] < A[right+1]) { //找到山顶 right++;}if (right < n-1 && A[right] > A[right+1]) { while (right < n - 1 && A[right] > A[right+1]) { //开始找右山脚 right++;}ans = max(ans, right-left+1);}}left = right;}return ans;}
};

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