我們把陣列 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，
示例 1：
輸入：[2,1,4,7,3,2,5]
輸出：5
解釋：最長的 “山脈” 是 [1,4,7,3,2]，長度為 5，
示例 2：
輸入：[2,2,2]
輸出：0
解釋：不含 “山脈”，
提示：
0 <= A.length <= 10000
0 <= A[i] <= 10000
解題思路：
可以用動態規劃的思想解決這道題，一個left容器統計左邊能延展的距離，right資料統計右邊能延展的距離，如果左右兩邊都能延展，那么這就是一個山峰，找到最長的山峰即可，代碼如下：
class Solution {
public:
int longestMountain(vector<int>& A) {
int n = A.size();
if(A.empty()){
return 0;
}
vector<int> left(n);
for(int i = 1; i < n ; i ++){
left[i] = A[i - 1] < A[i] ? left[i - 1] + 1 : 0;
}
vector<int> right(n);
for(int i = n - 2; i >= 0 ; i --){
right[i] = A[i + 1] < A[i] ? right[i + 1] + 1 : 0;
}
int ans = 0;
for(int i = 0; i < n; i ++){
if(left[i] > 0 && right[i] > 0){
ans = max(ans, left[i] + right[i] + 1);//左邊的加上右邊的還有中間的一個最高峰
}
}
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/194727.html
標籤：其他