Code Kata # 1


質問する


パラメータheightは数値からなる配列です.グラフィックで表すとy軸の値です.
高さの値.
[1,8,6,2,5,4,8,3,7]を下図に示します.

そのグラフに水があるとき、水を入れることができる最大面積の値を返してください.

家庭


配列の長さは2より大きい.

Solution


私が初めて書いたコードは以下の通りです.
def get_max_area(height):
  list=[]
  for i in range(len(height)):
    for j in range(len(height)):
      if j>i:
        list.append((j-i)*min(height[i],height[j]))
  return max(list)
(x 1,y 1),(x 2,y 2)という座標で考えると、
水の面積は(x 2−x 1)*(y 1,y 2の最小値)と表すことができる.
空のリストを作成し、リストの長さに等しい二重ループを返します.(j-i)を横方向、min(height[i],height[j])を縦方向として、全面積の値を計算します.
最大値を返すように解決します.
しかしそうすれば高さというリストの長さが長く、
問題は、その長さの平方を計算しなければならないことです.
この問題を解決するために、両方からアプローチする解決方法があります.
(私が解決したのではありません.)
def get_max_area(height):
  L = 0 # 처음 index
  R = len(height) - 1 # 가장 끝 index
  res = 0 # 초기 넓이
  while L < R: # 왼쪽 index가 오른쪽 index보다 작을때까지
    area = (R - L) * min(height[L], height[R]) # 넓이를 구하여 값을 저장
    res = max(area,res) # 기존 넓이와 비교하여 값을 저장
    if height[L] < height[R]: # 왼쪽 index 높이가 오른쪽 index 높이보다 작다면
      L += 1 # 다음 왼쪽 index와 비교
    else:
      R -= 1 # 그전 오른쪽 index와 비교
  return res
これなら、リストの長さを比較するだけで解決できます.