i071 - 風景 (Landscape)
題目描述
題目給定一個包含 n 個整數的陣列 a，以及一個整數 m。目標是計算從 m 位置向左右兩邊延伸，有多少個位置上的數值比目前的最大值還要大。
解題思路
這題可以利用貪心法解決。首先，讀取陣列 a 和整數 m。然後，從 m 的左邊開始遍歷，如果遇到比目前最大值 t 大的數，就更新 t 並將答案 ans 加一。接著，從 m 的右邊開始遍歷，重複相同的操作。最後輸出答案 ans。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int n,m,a[1005],ans;
int main(){
cin >> n >> m;
for(int i=1;i<=n;++i){
cin >> a[i];
}
for(int i=m-1,t=a[m];i>0;--i){
if(a[i]>t){
t=a[i];
++ans;
}
}
for(int i=m+1,t=a[m];i<=n;++i){
if(a[i]>t){
t=a[i];
++ans;
}
}
cout << ans;
}