So the question is, how can we do better?
One approach may be to use another List, or another stack to only track the local minimum. If the pushed node is smaller than the minimum of all existing nodes in the stack, push the node to the second stack. So for (0, 1, 2, 3, 4), we will have another list/stack only contains (0).
class MinStack { ListNode head; ListNode currMin; public MinStack() { head = null; currMin = null; } public MinStack(int val) { head = new ListNode(val); currMin = new ListNode(val); } public void push(int x) { if (head == null) { head = new ListNode(x); currMin = new ListNode(x); } else { ListNode node = new ListNode(x); node.next = head; head = node; //if there are two nodes with the same minimum value in the stack, //if we delete the first one, or the one pushed in later, the minimum //of the stack is still the same value, thus we need to push the node //to the min stack as long as it equals the minimum if (x <= currMin.val) { //need to create a new node and push it //to the second list, //otherwise the current node's next will points to next min //because we override it with the previous min ListNode tmp = node; tmp.next = currMin; currMin = tmp; } } } public void pop() { if (head == null) return; if (currMin.val == head.val) { currMin = currMin.next; } head = head.next; } public int top() { if (head == null) return -1; return head.val; } public int getMin() { if (head == null) return -1; return currMin.val; } private class ListNode{ int val; ListNode next; public ListNode(int val) { this.val = val; next = null; } } }
No comments:
Post a Comment