2021/07/31
はじめに
heightという配列が与えられ，そこにトラップされる水の総量を算出する問題．
ここでは，height[i]の値は，位置iにおけるブロック（壁？）の高さを表しており，水より高さの大きいブロックに囲まれていないと水はトラップしない．
コード全文
int trap(vector<int>& height) {
if(height.size() < 2) return 0;
vector<int> right_max (height.size());
right_max.back() = height.back();
for (int i=height.size()-2; i!=-1; --i) {
right_max[i] = max(right_max[i+1], height[i]);
}
int left_max = height[0];
int trapped_water = 0;
for (int i=1; i<height.size()-1; ++i) {
int min_wall = min(left_max, right_max[i+1]);
int water = min_wall - height[i];
if (water > 0) trapped_water += water;
left_max = max(left_max, height[i]);
}
return trapped_water;
}
解説
今回は，ある地点から見た左右の高さの最大値がわかれば，その位置にトラップする水の高さが分かるため，あらかじめ最大値をメモすることで対応する．
また，左からトラップする水の量を算出していき加算する関係上，左方向の最大の高さはループ上で求めることができるため，左方向だけ配列として準備して解いた．
関数
heightの長さが２よりも小さい場合は，トラップすることはないため，0となるのは明白であり，早期リターンする．
int trap(vector<int>& height) {
if(height.size() < 2) return 0;
右方向の最大高さを準備
ある地点から右方向の最大高さを求めたい場合，heightだけを使うと線形時間 O(N)の処理となり，全体のループの中に入れると O(N*N)となってしまう．
それに対し，一度走査して，最大値を更新しながら求めて保存していくことで，O(N)一度きりの処理となる．
vector<int> right_max (height.size());
right_max.back() = height.back();
for (int i=height.size()-2; i!=-1; --i) {
right_max[i] = max(right_max[i+1], height[i]);
}
変数準備
left_maxは，左方向のブロックの最大高さを格納する．ループする毎に更新する値とする．
trapped_waterは，関数が戻す値であり，ここにはトラップされる水の総量を加算的に格納する．
int left_max = height[0];
int trapped_water = 0;
ループ
位置iでの囲まれるブロックの高さを準備する．
左右の壁の低い方に水が流れていかなければ水がトラップするため，低い方のみ使う．
for (int i=1; i<height.size()-1; ++i) {
int min_wall = min(left_max, right_max[i+1]);
トラップされる水を加算
位置iのブロック高さが左右のブロックに囲まれている場合は，その差分がその位置でトラップされる水の量になる．
int water = min_wall - height[i];
if (water > 0) trapped_water += water;
左方向の最大高さを更新
left_max = max(left_max, height[i]);
}
戻り値
return trapped_water;
}
おわりに
解いてから気づいたが，この問題は Hard らしい．Medium や Hard の問題は難しくて諦めることが多かったので，解けて嬉しい．