#170MediumDesign· Stack with Constant-Time Minimum

Trail Minimum Altitude Stack

A hiking app records the altitude at each checkpoint as the walker advances along a trail, and removes the latest checkpoint when the walker retraces a step. At any moment the app must be able to show the **lowest altitude among the checkpoints currently recorded**. Design a class `TrailRecorder` that supports these operations, each in **O(1)** time: - `TrailRecorder()` creates an empty recorder. - `push(altitude)` records a new checkpoint at the end of the trail. - `pop()` removes the most recent checkpoint. - `top()` returns the altitude of the most recent checkpoint. - `lowest()` returns the lowest altitude among the checkpoints currently recorded. `pop`, `top` and `lowest` are only called when at least one checkpoint is recorded.

Input format

`operations`: the method names in call order (the first is the constructor); `arguments`: the argument list of each call.

Output format

One value per operation: `null` for the constructor, `push` and `pop`; the altitude for `top` and `lowest`.

Examples

Input: operations = ["TrailRecorder", "push", "push", "push", "lowest", "pop", "top", "lowest"], arguments = [[], [120], [80], [95], [], [], [], []]

Output: [null, null, null, null, 80, null, 80, 80]

After pushing 120, 80 and 95 the lowest is 80. Removing the checkpoint at 95 leaves 120 and 80: top is 80 and the lowest is still 80.

Input: operations = ["TrailRecorder", "push", "push", "pop", "lowest", "top"], arguments = [[], [50], [10], [], [], []]

Output: [null, null, null, null, 50, 50]

Removing the checkpoint at 10 (the old minimum) means the lowest altitude is back to 50.

Constraints

-2^31 <= altitude <= 2^31 - 1
At most 3 * 10^4 operations
`pop`, `top` and `lowest` are called only on a non-empty recorder.

#stack
#design
#data-structure