はじめに

---

vector<int> heightが与えられ、インデックスの差を横幅、heightを高さと考えた時の、水が入る最大量を求める問題．

この問題は、LeetCode上に例画像付きで出題されているので、そちらを見たほうがわかりやすいだろう。 水が入る最大量とは、「二つの要素を指定した時の最大の直方体面積」と考えるとわかりやすい。

コード全体

---

int maxArea(vector<int>& height) {
  int maxProduct = 0;
  int i = 0;
  int j = height.size() - 1;
  while(i < j){
    if(height[i]<height[j]){
      maxProduct = max(maxProduct, (j-i)*height[i++]);
    }else{
      maxProduct = max(maxProduct, (j-i)*height[j--]);
    }
  }
  return maxProduct;
}

解説

---

LeetCode上の"Solution"にアニメーションと共に解説が書かれているためそちらを見たほうが良いだろう。

左右端を最初の値として、面積を出す。

int maxArea(vector<int>& height) {
  int maxProduct = 0;
  int i = 0;
  int j = height.size() - 1;

左右が入れ替わらない限り、height[i]とheight[j]の小さいほうを内側にずらしていく。 その時、横を(j-i)と、縦をheight[i]/height[j]の小さいほうとする。 そして、maxProductを値が大きい方へと更新する。

  while(i < j){
    if(height[i]<height[j]){
      maxProduct = max(maxProduct, (j-i)*height[i++]);
    }else{
      maxProduct = max(maxProduct, (j-i)*height[j--]);
    }
  }

最後に、maxProductを返す。

  return maxProduct;
}