-
Notifications
You must be signed in to change notification settings - Fork 19
/
MinStack.java
109 lines (95 loc) · 3.34 KB
/
MinStack.java
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
97
98
99
100
101
102
103
104
105
106
107
108
109
package oj.leetcode;
import java.util.Stack;
/*
* Design a stack that supports push, pop, top, and retrieving the
* minimum element in constant time.
* push(x) -- Push element x onto stack.
* pop() -- Removes the element on top of the stack.
* top() -- Get the top element.
* getMin() -- Retrieve the minimum element in the stack.
*
* 1. ���ÿ��push��ʱ��ά���������� ���Ƿ�����ջ�����ʣ�ֻ��֤getMin�dz���ʱ�临�Ӷȣ�
* 2.����ķ����� ���� ����ջ��������һ��ջ�������ʱ�����Сֵ
* ջ�յ�ʱ����ô���������׳��쳣��cannot find symbol: class NoSuchElementException
* ���Բ��ô����õײ��Stack�������쳣��
*
* �����Ŀ���ȸ������� -
* Design a queue that supports push_rear, pop_front, and get_min in O(1).
* Would that be elegantly possible too?
*
* �����Ŀ - Sliding Window Maximum
*/
/**
* 使用2个stack,其中一个用来维护最小值
*/
public class MinStack {
Stack<Integer> storage = new Stack<Integer>();
Stack<Integer> currentMinStack = new Stack<Integer>();
public void push(int x) {
if (storage.isEmpty() || x <= currentMinStack.peek()) {
currentMinStack.push(x);
}
storage.push(x);
}
public void pop() {
if (storage.isEmpty())
return;
int x = storage.pop();
if (x == currentMinStack.peek())
currentMinStack.pop();
}
public int top() {
return storage.peek();
}
public int getMin() {
return currentMinStack.peek();
}
public static void main(String[] args) {
MinStack ms = new MinStack();
ms.push(2147483646);
ms.push(2147483646);
ms.push(2147483647);
System.out.println(ms.top());
System.out.println(ms.top());
System.out.println(ms.getMin());
ms.pop();
System.out.println(ms.getMin());
ms.pop();
ms.push(2147483647);
System.out.println(ms.top());
System.out.println(ms.getMin());
ms.push(-2147483648);
System.out.println(ms.top());
System.out.println(ms.getMin());
System.out.println(ms.top());
System.out.println(ms.getMin());
/*
System.out.println(ms.getMin());
System.out.println(ms.getMin());
ms.pop();
ms.pop();
System.out.println(ms.getMin());
ms.pop();
System.out.println(ms.getMin());
ms.pop();
ms.pop();
System.out.println(Integer.MAX_VALUE);
*/
}
}
/*
�𰸽�����
Consider space-time tradeoff.
How would you keep track of the minimums using extra space?
Make sure to consider duplicate elements.
O(n) runtime, O(n) space �C Extra stack:
Use an extra stack to keep track of the current minimum value.
During the push operation we choose the new element or the current minimum,
whichever that is smaller to push onto the min stack.
O(n) runtime, O(n) space �C Minor space optimization:
If a new element is larger than the current minimum,
we do not need to push it on to the min stack. When we perform
the pop operation, check if the popped element is the same as the
current minimum. If it is, pop it off the min stack too.
*
* */