leetcode11: rust

少しずつrustに慣れてきて問題を解くのがちょっと楽しくなってきた頃

気になるところが少しでもあれば 絶対に 気兼ねなくマサカリ投げてください

11 container with most water

長さnの整数の配列heightが与えられ、i,jが
$0 \le i<j<n$
を満たす

//擬似コード
width=j-i
height=max(height[i],height[j])
square=width*height

としたときsquareの最大値を返す

impl Solution {
   pub fn max_area(height: Vec<i32,>,) -> i32 {
      let mut tall_j = 0;
      let mut tall_i = 0;
      let mut wide = height.len() - 1;
      let mut square = 0;
      let mut i = 0;
      loop {
         if i >= height.len() {
	    break;
	 }
	
	 if height[i] <= tall_i {
	    while height[i] <= tall_i {
	       if i >= wide {
	          return square;
	       } else {
	          i += 1;
	       }
	    }
	 }
	 tall_i = height[i];
	 let mut j = wide;
	 loop {
	    if i >= j {
	       break;
	    }
	
	    if height[j] < tall_j {
	       while height[j] < tall_j {
		  if i >= j {
		     break;
		  } else {
		     j -= 1;
		  }
	       }
	       continue;
	    }
	    let cmp = (j - i) as i32 * height[i].min(height[j],);
	    if square < cmp {
	       tall_j = height[j];
	       wide = j;
	       square = cmp;
	    }
	    j -= 1;
	 }
	 i += 1;
      }
      square
   }
}

note

自分の提出した回答があまりにも汚かったため読む気が失せた。代わりにMost Votedな回答
（これ以降は、スマートな解答と呼ぶことにする）
を参考に解き直し。

impl Solution {
   pub fn max_area(height: Vec<i32,>,) -> i32 {
      let (mut i, mut j, mut water,) = (0, height.len() - 1, 0,);
      while i < j {
	 water = water.max((j - i) as i32 * height[i].min(height[j],),);
	 if height[i] > height[j] {
	    j -= 1;
	 } else {
	　 　i += 1;
	 }
      }
      water
   }
}

自分の解答がなぜああなってしまったか分析

端的にいうと、あり得ない場合のことを考えて沼っていた

まずスマートな方はwhileループを回す毎にjを1減らす or iを1増やすという操作をしている。
一方自分の解答では、loopが二重になっている上、
内側のループでは毎回j=height.len()で始まっている。
これは以下の様なケースを想定していた。

例えば、あるi=a,j=bでwaterが最大値になったとする。
この時height[a]<height[b]だったとすると、
（height[b]>height[a]としてもいい。というかi,jが入れ替わるだけなのでどっちでも良い）
スマートな方ではi+=1されて次のループに移る。

ここで仮にheight[b+1]>height[b] かつ height[b]<height[a+1]だとしたら、
(a,b)の組より(a+1,b+1)の組の方がwaterは大きくなる。
しかしjは増やすことができないのでスマートな回答は間違った値を返すのではないか

もちろんこれは起こり得ない。そもそもj=b+1がj=bになったということはheight[x]>height[b+1]となるx(≤a)が存在する必要がある。
このとき、height[b+1]>height[b]>height[a]なので(x,b+1)の組の方が(a,b)の組よりwaterが大きい必要があるが、これは

あるi=a,j=bでwaterが最大値になった

という前提と矛盾しているのでheight[b+1]>height[b] かつ height[b]<height[a+1]という仮定はそもそも有り得ないとわかる。