資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中陣列中的最長山脈
考慮任何（連續）子陣列 B（A 的子陣列）稱為山脈，如果滿足以下屬性：
- B 的大小 >= 3
- 存在某個 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
假設我們有一個整數陣列 A；我們必須找到最長山脈的長度。如果不存在山脈，則必須返回 0。因此，如果輸入類似於 [2,1,4,7,3,2,5]，則結果將為 5。因此，最大的山脈將是 [1,4,7,3,2]，其長度為 5。
為了解決這個問題，我們將遵循以下步驟：
- ret := 0，n := 陣列 a 的大小
- i := 0 到 n – 1，i 增加 j + 1
- j := i
- down := false，up := false
- 當 j + 1 < n 且 a[j + 1] > a[j] 時
- up := true 並將 j 增加 1
- 當 up 為 true 且 j + 1 < n 且 a[j + 1] > a[j] 時
- down := true 並將 j 增加 1
- 如果 up 和 down 都為 true，則將 ret 設定為 j – i + 1 和 ret 的最大值，將 j 減 1
- 返回 ret。
讓我們看看以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestMountain(vector<int>& a) {
int ret = 0;
int n = a.size();
int j;
for(int i = 0; i < n; i = j + 1){
j = i;
bool down = false;
bool up = false;
while(j + 1 < n && a[j + 1] > a[j]) {
up = true;
j++;
}
while(up && j + 1 < n && a[j + 1] < a[j]){
down = true;
j++;
}
if(up && down){
ret = max(j - i + 1, ret);
j--;
}
}
return ret;
}
};
main(){
vector<int> v = {2,1,4,7,3,2,5};
Solution ob;
cout << (ob.longestMountain(v));
}輸入
[2,1,4,7,3,2,5]
輸出
5
更新於: 2020 年 5 月 5 日
452 次瀏覽
廣告