h206 - 強者就是要戰，但......什麼才是強者呢？
題目描述
題目給定一個包含 N 個相異正整數的陣列，其中 N 是一個 2 的冪。目標是找到最強者，最強者的定義是透過遞迴的方式，將陣列不斷分割成左右兩半，並根據當前層級的奇偶性決定比較方式（奇數層級取最大值，偶數層級取最小值）。
解題思路
這題的核心是使用分治法 (Divide and Conquer) 搭配遞迴 (Recursion) 來解決。dfs 函式負責遞迴地分割陣列，並根據層級 b 的奇偶性來決定如何比較左右兩半的結果。如果 b 是奇數，則取左右兩半的最大值；如果 b 是偶數，則取左右兩半的最小值。遞迴的終止條件是當左邊界等於右邊界時，直接返回該元素的值。
複雜度分析
- 時間複雜度: O(N)。因為每次遞迴都會將問題規模減半，總共需要遞迴 log2(N) 層，每層需要 O(1) 的時間進行比較，因此總時間複雜度為 O(N)。
- 空間複雜度: O(log N)。這是因為遞迴的深度為 log2(N)，每一層遞迴都需要額外的空間來儲存函數調用信息。
程式碼
#include <iostream>
using namespace std;
int a[1025],n;
int dfs(int l,int r,int b){
if(l==r)return a[l];
int m=(l+r)/2,lv=dfs(l,m,b+1),rv=dfs(m+1,r,b+1);
if(b%2)return max(lv,rv);
return min(lv,rv);
}
int main(){
cin >> n;
for(int i=0;i<n;++i)
cin >> a[i];
cout << dfs(0,n-1,1);
}