An accepted Java solution with two singly linked lists and "unit" tests


  • -1
    F
    class MinStack {
        private ListNode top;
        private ListNode min;
    
        public void push(int x) {
            top = new ListNode(x, top);
    
            if (min == null || x <= min.getValue()) {
                min = new ListNode(x, min);
            }
        }
    
        public void pop() {
            int value = top.getValue();
    
            if (value == getMin()) {
                min = min.getNext();
            }
    
            top = top.getNext();
        }
    
        public int top() {
            return top.getValue();
        }
    
        public int getMin() {
            return min.getValue();
        }
    
    }
    
    class ListNode {
        private final int value;
        private final ListNode next;
    
        public ListNode(int value) {
            this(value, null);
        }
    
        public ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }
    
        public int getValue() {
            return value;
        }
    
        public ListNode getNext() {
            return next;
        }
    
        public boolean hasNext() {
            return next != null;
        }
    
    }
    

    And "unit" tests

    public class MinStackTest {
        private MinStack minStack = new MinStack();
    
        @Test(expected = NullPointerException.class)
        public void itShouldThrowNoSuchElementExceptionIfPoppedOnEmptyStack() {
            minStack.pop();
        }
    
        @Test(expected = NullPointerException.class)
        public void itShouldThrowNoSuchElementExceptionIfToppedOnEmptyStack() {
            minStack.top();
        }
    
        @Test
        public void itShouldPushAndTopAndPopValues() {
            minStack.push(4);
            minStack.push(1);
            minStack.push(3);
            minStack.push(2);
    
            assertThat("Popped element mismatch", minStack.top(), is(2));
            minStack.pop();
            assertThat("Popped element mismatch", minStack.top(), is(3));
            minStack.pop();
            assertThat("Popped element mismatch", minStack.top(), is(1));
            minStack.pop();
            assertThat("Popped element mismatch", minStack.top(), is(4));
            minStack.pop();
        }
    
        @Test(expected = NullPointerException.class)
        public void itShouldThrowNullPointerExceptionIfGotMinOnEmptyStack() {
            minStack.getMin();
        }
    
        @Test
        public void itShouldPushAndPopAndSupportGetMin() {
            minStack.push(8);
            minStack.push(5);
            minStack.push(6);
            minStack.push(4);
            minStack.push(3);
            minStack.push(9);
            minStack.push(2);
            minStack.push(7);
            minStack.push(2);
            minStack.push(6);
    
            assertThat("Min element mismatch", minStack.getMin(), is(2));
            minStack.pop();
            assertThat("Min element mismatch", minStack.getMin(), is(2));
            minStack.pop();
            assertThat("Min element mismatch", minStack.getMin(), is(2));
            minStack.pop();
            assertThat("Min element mismatch", minStack.getMin(), is(2));
            minStack.pop();
    
            assertThat("Min element mismatch", minStack.getMin(), is(3));
            minStack.pop();
            assertThat("Min element mismatch", minStack.getMin(), is(3));
            minStack.pop();
    
            assertThat("Min element mismatch", minStack.getMin(), is(4));
            minStack.pop();
    
            assertThat("Min element mismatch", minStack.getMin(), is(5));
            minStack.pop();
            assertThat("Min element mismatch", minStack.getMin(), is(5));
            minStack.pop();
    
            assertThat("Min element mismatch", minStack.getMin(), is(8));
            minStack.pop();
        }
    
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.