leetcode845.数组中的最长山脉

题目

把符合下列属性的数组 arr 称为 山脉数组 ：

arr.length >= 3
存在下标i（0 < i < arr.length - 1），满足
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。

示例 1：

输入：arr = [2,1,4,7,3,2,5]
输出：5
解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。

示例 2：

输入：arr = [2,2,2]
输出：0
解释：不存在山脉子数组。

提示：

1 <= arr.length <= 104
0 <= arr[i] <= 104

解答

三指针法

首先，我们可以初始化三个指针：left、right和peak。
- left指针指向山脉数组的起点，即数组的第一个元素。
- right指针指向山脉数组的终点，即数组的最后一个元素。
- peak指针指向山脉数组的顶峰。
我们可以通过移动right指针来找到山脉数组的终点。当数组的下一个元素比当前元素大的时候，我们可以继续移动right指针。如果下一个元素比当前元素小，我们将找到了山脉数组的终点。
一旦我们找到了山脉数组的终点，我们需要移动left指针。我们需要找到山脉数组的起点，即数组的第一个元素。我们可以通过移动left指针来找到山脉数组的起点。当数组的下一个元素比当前元素大的时候，我们可以继续移动left指针。
当我们找到山脉数组的起点和终点后，我们需要更新peak指针的位置。我们可以通过遍历山脉数组的起点到终点之间的元素，找到最大的元素，并更新peak指针的位置。
最后，我们可以计算山脉数组的长度，即右边界(right)减去左边界(left)再加1。如果山脉数组的长度大于等于3，就返回该长度；否则，返回0。

class Solution {
public:
    int longestMountain(vector<int>& A) {
        int n = A.size();
        int left = 0, right = 0, peak = 0;
        int longestMountainLength = 0;

        while (left < n) {
            right = left;
            // 找到山脉数组的终点
            if (right + 1 < n && A[right] < A[right + 1]) {
                while (right + 1 < n && A[right] < A[right + 1]) {
                    right++;
                }
                // 找到山脉数组的起点
                if (right + 1 < n && A[right] > A[right + 1]) {
                    peak = right;
                    while (peak + 1 < n && A[peak] > A[peak + 1]) {
                        peak++;
                    }
                    // 更新最长山脉的长度
                    longestMountainLength = max(longestMountainLength, peak - left + 1);
                }
            }
            left = max(right, left + 1);
        }

        return longestMountainLength >= 3 ? longestMountainLength : 0;
    }
};

仅用一趟扫描,并仅用O(1)空间复杂度解决问题

解题思路：

初始化变量：
- up：表示上升的长度（山脉的左半边）
- down：表示下降的长度（山脉的右半边）
- maxLen：表示最长山脉数组的长度
从数组的第二个元素开始遍历：
- 如果当前元素 A[i] 大于前一个元素 A[i-1]，则表示处于上升阶段，递增 up 的值，同时重置 down 的值为0。
- 如果当前元素
```
A[i]
```
  小于前一个元素
```
A[i-1]
```
  ：
  - 如果 up 大于0，表示已经处于山脉的下降阶段，递增 down 的值。
  - 如果 up 等于0，表示还没有开始上升阶段，不进行任何操作。
当 down 大于0时，表示找到了山脉数组的终点，更新 maxLen 的值。然后将指针移动到山脉数组的下一个元素，即 i 加1，并重置 up 和 down 的值为0。
最后返回 maxLen，即为最长山脉数组的长度。

class Solution {
public:
    int longestMountain(vector<int>& A) {
        int n = A.size();
        int up = 0, down = 0;  // 上升和下降的长度
        int maxLen = 0;  // 最长山脉数组的长度

        for (int i = 1; i < n; i++) {
            if (A[i] > A[i-1]) {  // 上升阶段
                if (down > 0) {  // 如果之前处于下降阶段，则重置上升和下降长度
                    up = 0;
                    down = 0;
                }
                up++;  // 递增上升长度
            } else if (A[i] < A[i-1]) {  // 下降阶段
                if (up > 0) {  // 如果之前处于上升阶段
                    down++;  // 递增下降长度
                    maxLen = max(maxLen, up + down + 1);  // 更新最长山脉数组的长度
                }
            } else {  // 平稳阶段，重置上升和下降长度
                up = 0;
                down = 0;
            }
        }

        return maxLen;
    }

};