pushとpopに加えて、最小の要素を返す関数minを持つスタックをデザインしてください。ただい、push、pop、min関数は全てO(1)の実行時間になるようにしてください。
解答
格納するノードのそれぞれに最小値をもたせておけば、容易に最小値を知ることができる。よって、ノードを追加するごとにその情報を持たせておき、最小値を調べたい時は一番上の要素を見れば良い。
Java
1public class StackWithMin extends java.util.Stack<NodeWithMin> { 2 public void push(int value) { 3 int newMin = Math.min(value, min()); 4 super.push(new NodeWithMin(value, newMin)); 5 } 6 7 public int min() { 8 if(this.isEmpty()) { 9 return Integer.MAX_VALUE; //エラー値 10 } else { 11 return peek().min; 12 } 13 } 14} 15 16class NodeWithMin { 17 public int value; 18 public int min; 19 public NodeWithMin(int v, int min) { 20 value = v; 21 this.min = min; 22 } 23}
質問は2点あります。
まず、1点目ですが、minメソッドの中に用いられているisEmptyメソッドについてです。
このメソッドは一体どのクラスのメソッドなのでしょうか?
thisとあるのですが、StackWithMinクラスにも親クラスであるStackクラスにもisEmptyメソッドはないようでした。(StackクラスにはEmptyメソッドはありました)
そうすると、このメソッドはどこのメソッドなのでしょうか?
続いて、2点目です。NodeWithMinクラスではコンストラクタで
二つの引数を受け取るコンストラクタが定義されいます。
そのうち、minはthisが使われていますが、valueはthisが使われておりません。
これには一体どのような意味があるのでしょうか?
コンストラクタに関しては全てthisを使うべきじゃないのかなと思っているのですが。
以上、2点回答よろしくお願いします。
回答3件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2016/08/28 10:32
2016/08/28 10:58
退会済みユーザー
2016/08/28 12:49
2016/08/28 13:16
退会済みユーザー
2016/08/29 07:46
2016/08/29 15:52
退会済みユーザー
2016/08/30 04:08