タイトルで述べたように、挿入の削除とgetMIn時間にO（1）時間しかかからないデータ構造を定義する必要があります。スペースの制約はありません。
私はSOで同じものを検索しましたが、見つけたのはO（1）時間での挿入と削除だけです。スタックでもそうです。私はスタックオーバーフローで前の投稿を見ました彼らが言うのはハッシュだけです...
O（1）時間でのgetMInの分析では、スタックがあるO（1）時間
での挿入と削除にヒープデータ構造を使用できます...
したがって、目標を達成するには、ヒープデータ構造とスタックを微調整する必要があると思います...この状況にハッシュ手法を追加するにはどうすればよいですか...
ハッシュテーブルを使用する場合、ハッシュ関数はハッシュの観点から状況を分析する方法のようになります...良い参照があれば幸いです...
挿入と削除がO（1）の複雑さであるという最初の仮定に従えば（上に挿入し、上から削除/ポップするだけの場合、スタックは正常に機能します）、getMinに最小値を返すようにします一定の時間で、あなたは何とかして分を保存する必要があるでしょう。メンバー変数に最小値を追跡させた場合、スタックから削除された場合はどうなりますか？次の最小値、またはスタックに残っているものに関連する最小値が必要になります。これを行うには、スタック内の要素に最小と思われるものを含めることができます。スタックはリンクリストによってコードで表されるため、リンクリスト内のノードの構造体は次のようになります。
struct Node
{
int value;
int min;
Node *next;
}
リストの例を見ると、7-> 3-> 1->5->2です。これがどのように構築されるかを見てみましょう。最初に値2を（空のスタックに）プッシュします。これは最初の数値であるため最小値です。これを追跡し、作成時にノードに追加します：{2、2}。次に、5をスタックにプッシュします（5> 2）。これにより、最小値は{5,2}と同じになり、{5,2}->{2,2}になります。次に、1を押し込み、1 <2なので、新しい最小値は1になり、{1、1}を押します。これで、{1,1}->{5,2}->{2,2}などになります。持ってる：
{7,1}-> {3,1}-> {1,1}-> {5,2}-> {2,2}
この実装では、7、3、および1をポップオフした場合、新しい最小値は2になります。また、ノードに比較と別の値を追加しただけなので、すべての操作は一定時間のままです。（C ++のpeek（）のようなものを使用するか、リストの先頭へのポインターを使用してスタックの先頭を確認し、そこで最小値を取得すると、一定時間でスタックの最小値が得られます。 ）。
この実装のトレードオフは、ノードに余分な整数が含まれることです。非常に大きなリストに1分または2分しかない場合は、メモリの浪費になります。この場合、別のスタックで分を追跡し、削除するノードの値をこのリストの一番上と比較し、一致する場合は両方のリストから削除することができます。追跡することがもっとあるので、それは本当に状況に依存します。
免責事項：これはこのフォーラムでの私の最初の投稿なので、少し複雑または言葉遣いである場合は申し訳ありません。また、これが「1つの真の答え」であると言っているわけではありませんが、最も単純で、質問の要件に準拠していると思います。常にトレードオフがあり、状況に応じてさまざまなアプローチが必要になります。
これは設計上の問題です。つまり、既存のデータ構造をどれだけ迅速に拡張できるかを確認したいと考えています。
あなたが知っていることから始めましょう：
hashtableここでは、それを行う1つの方法を紹介します。あなたが好む何か他のものを見つけるかもしれません。
main。ここにすべての要素を保存しますmins、最小値を追跡する場所を呼び出します。main、それもに追加しminsます。minsと同等の値を使用してマップに追加しaddToHeadます。mainも削除しminsます。2 * O（1）= O（1）getMin削除せずに単に覗いていることに注意してください。だから、の頭をのぞいてみてminsください。編集：
（@Andrew Tomazosに感謝します-Fathomling、もっと楽しみましょう！）
ハッシュテーブルへの挿入のコストはO（1）であることは誰もが知っています。しかし実際には、ハッシュテーブルを作成したことがある場合は、オーバーフローを回避するためにテーブルのサイズを2倍にし続ける必要があることを知っています。n個の要素を持つテーブルのサイズを2倍にするたびに、要素を再挿入してから、新しい要素を追加する必要があります。この分析によると、ハッシュテーブルに要素を追加するための最悪の場合のコストはO（n）であるように思われます。では、なぜそれがO（1）だと言うのでしょうか。すべての要素が最悪の場合をとるわけではないからです！実際、ダブリングが発生する要素のみが最悪の場合を取ります。したがって、n個の要素を挿入すると、次のようになりますn+summation(2^i where i=0 to lg(n-1))。n+2n = O(n)O(n)/n = O(1)
LinkedInHashMapに同じ原則を適用してみませんか？とにかくすべての要素をリロードする必要があります！したがって、2倍にするたびにmain、すべての要素をmain分単位で入力し、それらをで並べ替えますmins。次に、他のすべての場合について、上記のように進めます（箇条書きの手順）。
ハッシュテーブルは、O（1）での挿入と削除を提供します（スタックに穴を開けることができないため、スタックは提供しません）。ただし、O（1）にgetMinを含めることもできません。これは、要素の順序付けがO（n * Log（n））（定理）よりも速くなることはないためです。これは、それぞれのO（Log（n））を意味します。エレメント。
最小値へのポインタを保持して、O（1）にgetMinを含めることができます。このポインタは、最小値の挿入では簡単に更新できますが、削除では更新できません。ただし、削除を使用する頻度によっては、それを使用することをお勧めします。
述べられているように厳密に言えば、問題はおそらく不可能ですが、次のことを考慮してください。
タイプTが与えられた場合、値iが値j（T（i）<T（j）の場合）よりも小さくなるように、そのタイプのすべての可能な要素に列挙を配置します。（つまり、タイプTのすべての可能な値に順番に番号を付けます）
そのサイズの配列を作成します。
配列の要素を作成します。
struct PT
{
T t;
PT* next_higher;
PT* prev_lower;
}
二重リンクリスト（インデックスの順序、したがってソートされた順序）のストレージを維持しながら、要素を配列に挿入および削除します
これにより、一定のgetMinとdeleteが得られます。
挿入の場合、配列内の次の要素を一定時間で見つける必要があるため、ある種の基数検索を使用します。
配列のサイズが2^xの場合、x個の「スキップ」配列を維持します。配列iの要素jは、インデックスを作成するメイン配列の最も近い要素を指します（j << i）。
これにより、更新と検索に常に固定x数のルックアップが必要になるため、一定時間挿入されます。
これは指数空間を使用しますが、これは質問の要件によって許可されています。
トライを使用できます。トライには、挿入、削除、およびgetminの両方でO（L）の複雑さがあります。ここで、Lは、探している文字列（またはその他）の長さです。n（要素の数）に関しては一定の複雑さです。
ただし、大量のメモリが必要です。彼らは「スペースの制約がない」ことを強調したので、おそらくトライを考えていたのでしょう。：D
問題ステートメント「O（1）での挿入と削除はスタックがあります...」では、delete = pop（）と想定しているので、別のスタックを使用してminを追跡します。
algo：スタック1-通常のスタック; スタック2-最小スタック
スタック1にプッシュします。スタック2が空であるか、新しいアイテム<stack2.peek（）の場合は、スタック2にもプッシュします。
目的：いつでもstack2.peek（）は最小O（1）を与えるはずです
スタック1からのpop（）。ポップされた要素がstack2.peek（）と等しい場合、スタック2からのpop（）も同様です。