スタック面接の質問を PHP_PHP チュートリアルで解決する

はじめに

面接で質問がありました。質問の一般的な意味は次のとおりです。

2 つの通常のスタックを使用して特別なスタックを実装します。これにより、pop、push、min 関数はすべて複雑度 O(1) の操作になります。 min 関数は、現在のスタックの最小値を取得します。

最初の考え

1. (1)の操作としてmin関数を実装するには、その時の最初のアイデアは、現在の最小値を事前に計算することでしたので、現在のスタックに最小の要素を保存し、それを維持する値を使用することを考えました。これはプッシュおよびポップ操作中の値です。このように、min と Push は両方とも O(1) ですが、pop はそうではありません。現在のポップアップが最小値の場合は、O(1) ではない現在の要素の最小値を再度見つける必要があります。 。

2. さらに、上記の方法では別のスタックを使用しなかったため、図に示すように、ソートされた要素をスタックに格納し、プッシュおよびポップ操作中にこの順序付けされたスタックも維持することを考えました。

ただし、この場合、最小操作は O(1) ですが、プッシュ操作とポップ操作はこの順序付けられたスタックを維持する必要があるため、O(1) の複雑さを達成できるメソッドは思いつきません。

その時は、最小値の情報を別のスタックにキャッシュしておくべきだと思ったのですが、食事をしなかったのか何か分からず思考がフリーズしてしまいました。

正しい解決策

問題に遭遇して解決できないととても悔しかったので、スタックの特性をしっかり理解し、min演算で使用する最小値情報を効果的にキャッシュする方法を食事しながら考え始めました。

スタック操作の最大の特徴は、スタックの最上位の要素に対してのみ操作できることです。各スタック操作の最小値をキャッシュするために補助スタックを使用するという考えは正しくありません。このようにして、補助スタックの最上位要素が現在のスタックの最小値であるため、ポップ操作が実行されるたびに両側を一緒にポップできます。プッシュ操作では、プッシュされた要素と最上位要素を比較するだけで済みます。補助スタックの。このように、push、pop、min はすべて O(1) 操作です。写真に示すように:

テキストが明確ではないかもしれません。以下のコードは、配列を介してスタックをシミュレートする PHP 実装です。

リーリー

$obj = 新しい strack();出力は次のとおりです:

int(4)OK、要件は満たされました。

それを達成するための他のより良い方法がある場合は、教えてください^_^

http://www.bkjia.com/PHPjc/824668.html