最小栈
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) – Push element x onto stack.
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
public class MinStack
{
ArrayList data = new ArrayList();
ArrayList minValue = new ArrayList();
public MinStack()
{
}
public void Push(int x)
{
if (data.Count == 0)
{
minValue.Add(x);
}
else if (x < (int)minValue[minValue.Count - 1])
{
minValue.Add(x);
}
data.Add(x);
}
public void Pop()
{
var temp = data[data.Count - 1];
if (temp.Equals(minValue[minValue.Count - 1]))
{
minValue.RemoveAt(minValue.Count - 1);
}
data.RemoveAt(data.Count - 1);
}
public int Top()
{
return (int)data[data.Count - 1];
}
public int GetMin()
{
return (int)minValue[minValue.Count - 1];
}
}
利用两个栈来实现
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
public class MinStack
{
Stack<int> data = new Stack<int>();
Stack<int> minValues = new Stack<int>();
public MinStack()
{
}
public void Push(int x)
{
data.Push(x);
if(minValues.Count==0 ||x<=minValues.Peek())
{
minValues.Push(x);
}
}
public void Pop()
{
int value = data.Pop();
if (value == minValues.Peek())
minValues.Pop();
}
public int Top()
{
return data.Peek();
}
public int GetMin()
{
return minValues.Peek();
}
}
近期评论