leetcode 山脉合集

941. 有效的山脉数组

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

如果 A 满足下述条件，那么它是一个山脉数组：

• arr.length >= 3
• 在 0 < i < arr.length – 1 条件下，存在 i 使得：arr[0] < arr[1] < … arr[i-1] < arr[i]
• arr[i] > arr[i+1] > … > arr[arr.length – 1]

思路

• 注意全递增或者全递减不属于山脉

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if (arr.size() < 3) {
            return false;
        }
        int i = 0;
        while (i < arr.size()-1 && arr[i] < arr[i+1]) {
            i++;
        }
        //只有递减0；只有递增arr.size()-1
        if (i == 0 || i == arr.size()-1) {
            return false;
        }
        while (i < arr.size()-1 && arr[i] > arr[i+1]) {
            i++;
        }
        if (i == arr.size()-1) {
            return true;
        } else {
            return false;
        }
    }
};

852. 山脉数组的峰顶索引

找到山脉数组的山顶元素
山脉数组定义同上。

思路

• 比较简单，直接在上体基础上判断，本题一定存在山脉数组
• 找到第一个不满足递减序列的即可

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        if (arr.size() < 3) {
            return 0;
        }
        int i = 0;
        while (i < arr.size()-1 && arr[i] < arr[i+1]) {
            i++;
        }
        return i;
    }
};

845. 数组中的最长山脉

我们把数组 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。

思路

• 返回最长的山脉长度
• 注意需要是最长连续子数组

• 可以通过dp做，

  • left[i] 找到元素 i 向左侧最多可以扩展的元素个数
  • right[i] 找到元素 i 向右侧最多可以扩展的元素个数

class Solution {
public:
    int longestMountain(vector<int>& A) {
        if (A.size() < 3) {
            return 0;
        }
        vector<int> left(A.size());
        vector<int> right(A.size());

        for (int i = 0; i < A.size(); i++) {
            if (i == 0) {
                left[i] = 0;
                continue;
            }
            if (A[i-1] < A[i]) {
                left[i] = left[i-1] + 1;
            } else {
                left[i] = 0;
            }
        }

        for (int i = A.size()-1; i >= 0; i--) {
            if (i == A.size()-1) {
                right[i] = 0;
                continue;
            }
            if (A[i] > A[i+1]) {
                right[i] = right[i+1] + 1;
            } else {
                right[i] = 0;
            }
        }
        int res = INT_MIN;
        for (int i = 0; i < A.size(); i++) {
            if (left[i] > 0 && right[i] > 0) {
                res = max(res, right[i] + left[i] + 1);
            }
        }
        return res == INT_MIN ? 0 : res;
    }
};

如果是返回最长非连续子数组构成的山脉长度

输入：[2,1,4,3,6,7,9,4]
输出：6; 满足条件子数组是[1,3,6,7,9,4]

思路

• 找到最大值，最大值不能是首尾
• 最大值左边，对所有不满足递增的元素删除
• 最大值右边，对所有不满足递减的元素删除