共计 1622 个字符，预计需要花费 5 分钟才能阅读完成。
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]
思路
- 找到最大值，最大值不能是首尾
- 最大值右边，对所有不满足递增的元素删除
- 最大值左边，对所有不满足递加的元素删除
正文完
