Loading...
Loading...
Loading...
A hostel mess keeps a pile of meal tokens. Each token has a price, and new tokens always go on top of the pile. The mess manager often asks for the cheapest token in the pile, and the pile can hold up to 10^5 tokens.
You get q commands, one per line: - push x: put a token with price x on top. - pop: remove the top token. Print nothing, but if the pile is empty, print EMPTY. - top: print the price of the top token, or EMPTY if the pile is empty. - min: print the lowest price in the pile, or EMPTY if the pile is empty.
push x, pop, top or min.top and min command, and for every pop on an empty pile, in the order the commands appear.Example
Input
9 push 5 push 3 push 7 min top pop pop min top
Output
3 7 5 5
The lowest price is 3 until token 3 is popped. Then only 5 is left, so min and top both print 5.
Try the problem first. Open one hint at a time.
One variable for the lowest price is not enough. After a pop, the lowest price can go back to an older value.
Next to every token, remember the lowest price from the bottom of the pile up to that token.
Keep a second stack for these values and push and pop it together with the main stack.
Then min is just the top of the second stack.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor