最小値スタック

最小値スタック

push や pop のたびに、最小要素を即座に返せるスタックを作ります。

このチャレンジで学べること

generic な Stack<T> は任意の型で使えます。ここではその考え方を拡張して、整数のスタックが最小値も定数時間で返せるようにします。

操作を順番に処理してください:

min_stack_operations(operations) を実装してください。

operations: 操作列。

min 操作の答えを、順番に返してください。

1 ≤ 操作の数 ≤ 200,000

0 ≤ x ≤ 10^9

例 1

入力：
operations = ["push 5", "push 3", "min", "pop", "min"]

期待される出力：
expected = [3, 5]

入力：
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};

期待される出力：
std::vector<long long> expected = {3, 5};

入力：
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};

期待される出力：
long[] expected = new long[] {3, 5};

スタックに 5 と 3 があるとき、最小値は 3 です。3 を pop すると、5 だけが残ります: [3, 5].

例 2

入力：
operations = ["min", "pop", "push 7", "min"]

期待される出力：
expected = [-1, 7]

入力：
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};

期待される出力：
std::vector<long long> expected = {-1, 7};

入力：
string[] operations = new string[] {"min", "pop", "push 7", "min"};

期待される出力：
long[] expected = new long[] {-1, 7};

空のスタックでは -1 が返され、pop は無視されます。その後、最小値は 7 です: [-1, 7].

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

各値の隣に、その時点のスタックの最小値を記録します。

ヒント 2

すると現在の最小値は 2 つ目のスタックの一番上になります。

ヒント 3

空のときの pop は無視し、min には -1 を返します。

目安の計算量

時間 O(操作の数)、追加メモリ O(操作の数)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。