?941. 有效的山脈數(shù)組
難度：簡單
給定一個(gè)整數(shù)數(shù)組 arr，如果它是有效的山脈數(shù)組就返回 true，否則返回 false。
讓我們回顧一下，如果 arr 滿足下述條件，那么它是一個(gè)山脈數(shù)組：
- 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]
示例 1：
輸入：arr = [2,1]
輸出：false
示例 2：
輸入：arr = [3,5,5]
輸出：false
示例 3：
輸入：arr = [0,3,2,1]
輸出：true
提示：
- 1 < = a r r . l e n g t h < = 1 0 4 1 <= arr.length <= 10^4 1<=arr.length<=104
- 0 < = a r r [ i ] < = 1 0 4 0 <= arr[i] <= 10^4 0<=arr[i]<=104
??思路：雙指針
判斷是山峰，主要就是要嚴(yán)格的保存左邊到中間遞增的，及右邊到中間是遞增的。
- 這樣可以使用兩個(gè)指針，
left和right。 - 因?yàn)?
left和right是數(shù)組下標(biāo)，移動(dòng)的過程中注意不要數(shù)組越界； - 如果
left或者right沒有移動(dòng)，說明是一個(gè)單調(diào)遞增或者遞減的數(shù)組，依然不是山峰。
??代碼：(Java、C++)
Java
class Solution {
public boolean validMountainArray(int[] arr) {
int n = arr.length;
if (n < 3) return false;
int left = 0;
int right = n - 1;
// 嚴(yán)格遞增遍歷，注意防止越界
while (left < n - 1 && arr[left] < arr[left + 1]) left++;
// 嚴(yán)格遞減遍歷，注意防止越界
while (right > 0 && arr[right] < arr[right - 1]) right--;
// 如果left或者right都在起始位置，說明不是山峰
if (left == right && left != 0 && right != n - 1) return true;
return false;
}
}
C++
class Solution {
public:
bool validMountainArray(vector<int>& arr) {
int n = arr.size();
if (n < 3) return false;
int left = 0;
int right = n - 1;
// 嚴(yán)格遞增遍歷，注意防止越界
while (left < n - 1 && arr[left] < arr[left + 1]) left++;
// 嚴(yán)格遞減遍歷，注意防止越界
while (right > 0 && arr[right] < arr[right - 1]) right--;
// 如果left或者right都在起始位置，說明不是山峰
if (left == right && left != 0 && right != n - 1) return true;
return false;
}
};
?? 運(yùn)行結(jié)果：
?? 復(fù)雜度分析：
-
時(shí)間復(fù)雜度：
O
(
n
)
O(n)
O(n)，其中
n為數(shù)組arr的長度。 - 空間復(fù)雜度： O ( 1 ) O(1) O(1)。
題目來源：力扣。文章來源：http://www.zghlxwxcb.cn/news/detail-489148.html
放棄一件事很容易，每天能堅(jiān)持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁 / CSDN—力扣專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-489148.html
注： 如有不足，歡迎指正！
到了這里，關(guān)于(數(shù)組) 941. 有效的山脈數(shù)組 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
