|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
| 3 | +importjava.util.Deque; |
| 4 | +importjava.util.LinkedList; |
3 | 5 | importjava.util.Stack; |
4 | 6 |
|
5 | | -/** |
6 | | - * 155. Min Stack |
7 | | - * Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. |
8 | | -
|
9 | | - * push(x) -- Push element x onto stack. |
10 | | - * pop() -- Removes the element on top of the stack. |
11 | | - * top() -- Get the top element. |
12 | | - * getMin() -- Retrieve the minimum element in the stack. |
13 | | -
|
14 | | - * Example: |
15 | | - * MinStack minStack = new MinStack(); |
16 | | - * minStack.push(-2); |
17 | | - * minStack.push(0); |
18 | | - * minStack.push(-3); |
19 | | - * minStack.getMin(); --> Returns -3. |
20 | | - * minStack.pop(); |
21 | | - * minStack.top(); --> Returns 0. |
22 | | - * minStack.getMin(); --> Returns -2. |
23 | | - */ |
24 | | - |
25 | 7 | publicclass_155 { |
26 | 8 |
|
27 | 9 | publicstaticclassSolution1 { |
28 | 10 | classMinStack { |
29 | 11 | privateStack<Integer>stack; |
30 | 12 | privateintmin; |
31 | 13 |
|
32 | | -/** |
33 | | - * initialize your data structure here. |
34 | | - */ |
35 | 14 | publicMinStack() { |
36 | 15 | stack =newStack(); |
37 | 16 | min =Integer.MAX_VALUE; |
@@ -64,4 +43,45 @@ public int getMin() { |
64 | 43 | } |
65 | 44 | } |
66 | 45 | } |
| 46 | + |
| 47 | +publicstaticclassSolution2 { |
| 48 | +/** |
| 49 | + * We could store a pair onto the stack: the first element in the pair is the value itself, |
| 50 | + * the second element in the pair is the current minimum element so far seen on the stack. |
| 51 | + */ |
| 52 | +classMinStack { |
| 53 | +Deque<int[]>stack; |
| 54 | + |
| 55 | +publicMinStack() { |
| 56 | +stack =newLinkedList<>(); |
| 57 | + } |
| 58 | + |
| 59 | +publicvoidpush(intval) { |
| 60 | +if (!stack.isEmpty()) { |
| 61 | +int[]last =stack.peekLast(); |
| 62 | +intcurrentMin =last[1]; |
| 63 | +if (val <currentMin) { |
| 64 | +stack.addLast(newint[]{val,val}); |
| 65 | + }else { |
| 66 | +stack.addLast(newint[]{val,currentMin}); |
| 67 | + } |
| 68 | + }else { |
| 69 | +stack.addLast(newint[]{val,val}); |
| 70 | + } |
| 71 | + } |
| 72 | + |
| 73 | +publicvoidpop() { |
| 74 | +stack.pollLast(); |
| 75 | + } |
| 76 | + |
| 77 | +publicinttop() { |
| 78 | +returnstack.peekLast()[0]; |
| 79 | + } |
| 80 | + |
| 81 | +publicintgetMin() { |
| 82 | +returnstack.peekLast()[1]; |
| 83 | + } |
| 84 | + } |
| 85 | + |
| 86 | + } |
67 | 87 | } |