LeetCode 题解：845. Longest Mountain in Array

本文主要是介绍LeetCode 题解：845. Longest Mountain in Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Let’s call any (contiguous) subarray B (of A) a mountain if the following properties hold:

B.length >= 3
There exists some 0 < i < B.length - 1 such that B[0] < B[1] < … B[i-1] < B[i] > B[i+1] > … > B[B.length - 1] (Note that
B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

解题思路

从左往右遍历数组，子区间长度用 [ left, right] 表示，left 和 right 初始化为0，有五步操作：

**检测递增区间：**假如A[right + 1] > A[right]，说明序列递增，子区间右边界右移一位；否则，说明当前A[right]是此子序列的最大项，转至第二步。
假如 left 和 right 相等，说明子区间中不是以递增序列开始，整个子区间往右移一位，转至第一步；否则，转至第三步。
**检测递减区间：**假如A[right + 1] < A[right]，说明序列递减，子区间右边界右移一位；否则，说明当前A[right]是此子序列的最小项，转至第四步。
假如此时的 right 和初始值相等，说明子区间中不是以递减序列结束，清空子区间并从当前位置的下一位开始新的子区间，转至第一步；否则，转至第五步。
当前子区间的长度为right - left + 1，与当前最大子区间长度 maxCount 作比较。清空子区间并从当前位置的下一位开始新的子区间。若已经遍历完成，跳出循环并返回；否则，转至第一步。

C++代码

class Solution {
public:int longestMountain(vector<int>& A) {int left = 0, right = 0;int maxCount = 0, rec = 0;while(right < A.size()) {while(right < A.size() && A[right+1] > A[right]) right++;if(right == left) {left++;right++;continue;}rec = right;while(right + 1 < A.size() && A[right+1] < A[right]) right++;if(right == rec) {right++;left = right;continue;}maxCount = max(maxCount, right - left + 1);left = right;}return maxCount;}
};