Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1522
Question Name: Min In Stack
Question Description: implement a customized stack. It should provide a function min() to return the minimum value in the stack in O(1) time.
Input: the input might contain multiple test cases. Inside each test case, the first line includes one intergers N (1 <= N <= 1000000), saying the number of following instructions. The following N lines contain the instructions. Each instruction might be either:
s INTEGER: where s is the “push” command, and the INTEGER is an number as the paramter; OR
o: where o is the “pop” command.
Output: NULL if the stack is empty. Otherwise, print the minimum value after each instruction.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | Input: 7 s 3 s 4 s 2 s 1 o o s 0 Output: 3 3 2 1 2 3 0 |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/10/2014 * Last updated: 08/10/2014 * * Filename: MinInStack.java * Compilation: javac MinInStack.java * Execution: java MinInStack * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.EmptyStackException; import java.util.Stack; /** * Definie a stack with a function min(). min() will return the * minimum value in the stack. * @author Sheng Yu codesays.com */ public class MinInStack extends Stack<Integer> { /** The default serial version ID. */ private static final long serialVersionUID = 1L; /** Store the minimum values in the stacks. */ private Stack<Integer> minStack = new Stack<Integer>(); /** * Push the item to the stack, and record it if it's the smallest * item so far. * @param item the item to append at the end of the stack. * @return the pushed item. */ @Override public final Integer push(final Integer item) { if (minStack.empty() || item <= minStack.peek()) { minStack.push(item); } super.push(item); return item; } /** * Removes and return the Integer at the top of this stack. If it is * the minimum value so far, the minStack is also popped. * @return the Integer at the top of the stack. */ @Override public final Integer pop() { Integer toReturn = super.pop(); if (toReturn == minStack.peek()) { minStack.pop(); } return toReturn; } /** * Return the minimum value in current stack. * @return the minimum value in the stack. */ public final Integer min() { return minStack.peek(); } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(final String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int instructionCount = 0; MinInStack test = new MinInStack(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Start one test case. instructionCount = (int) st.nval; while (instructionCount-- > 0) { st.nextToken(); if (st.sval.equals("s")) { // PUSH st.nextToken(); test.push((int) st.nval); } else if (st.sval.equals("o")) { // POP try { test.pop(); } catch (EmptyStackException e) { assert true; // NOPE } } else { // Invalid command. throw new IllegalArgumentException(); } try { System.out.println(test.min()); } catch (EmptyStackException e) { // Empty stack. System.out.println("NULL"); } } } } } |