|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
Subscribe to see which companies asked this question.
|
题意：设计一个有MIN函数的栈。
|
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
|
public
class
MinStack {
private
Stack<Integer> stackData;
private
Stack<Integer> stackMin;
/** initialize your data structure here. */
public
MinStack() {
stackData=
new
Stack<Integer>();
stackMin=
new
Stack<Integer>();
}
public
void
push(
int
x) {
if
(stackMin.isEmpty()){
stackMin.push(x);
}
else
if
(x<=stackMin.peek()){
stackMin.push(x);
}
stackData.push(x);
}
/////这里貌似有点问题。。。。//包装类比较。。。。
public
void
pop() {
if
(stackData.peek().equals(stackMin.peek())){
stackMin.pop();
}
stackData.pop();
}
public
int
top() {
return
stackData.peek();
}
public
int
getMin() {
return
stackMin.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
|
PS:定义一个辅助栈。用于存放每一步的最小值。参见左老师的书P1。
本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1905453
