時間計算量O(n^2)の方法、O(n)の方法をそれぞれ紹介します。
O(n^2)の方法
int maxArea(vector<int>& height) {
int max_area = 0;
for (size_t i = 0; i < height.size(); i++) {
for (size_t j = height.size()-1; i < j; j--) {
const int current_area = std::min(height[i], height[j]) * (j - i);
max_area = std::max(current_area, max_area);
}
}
return max_area;
}問題文を読んでパッと思い浮かんだ方法です。とりあえずoutputは正しいものが出てきますが、LeetCodeでも仕事でもO(n^2)は避けたいところ……
O(n)の方法
結局「editional」を覗きました。
int maxArea(vector<int>& height) {
int max_area = 0;
size_t left = 0;
size_t right = height.size() - 1;
while (left < right) {
const int current_area = std::min(height[left], height[right]) * (right - left);
max_area = std::max(current_area, max_area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max_area;
}解説
LeetCodeの「editional」の記載が全てですが、一応記載すると、
最初は両端のheightからstartし、狭めていきながら面積を求めていく方法です。
ポイントは、左右のheightのindexを進める際に、低い方のみを中心に進めます。
高い方を中心へ進めても面積が増えることはないからです。
どっかの本で「自分で答えを探すならどうやるか」をコードに落とせば良い。と書いてあったのですが、なかなか難しいです。
以上です！