• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

leetcode 山脉合集

互联网 diligentman 5天前 7次浏览

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]

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

程序员灯塔
转载请注明原文链接:leetcode 山脉合集
喜欢 (0)