乐趣区

关于leetcode:leetcode-山脉合集

jiezi

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]

思路
  • 找到最大值，最大值不能是首尾
  • 最大值右边，对所有不满足递增的元素删除
  • 最大值左边，对所有不满足递加的元素删除
退出移动版