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]
思路
- 找到最大值，最大值不能是首尾
- 最大值右边，对所有不满足递增的元素删除
- 最大值左边，对所有不满足递加的元素删除