分享程序员开发的那些事...
更新时间：2022-09-20 23:35:44
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。
解题思路：把每次的最小元素都保存起来放到另外一个辅助栈里。
C#实现方式：
|
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
|
public class StackWithMin
{
private Stack<int> m_data;
private Stack<int> m_min;
#region 包含min函数的栈
/// 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。
/// 在该栈中，调用min、push及pop的时间复杂度都是O(1).
///
public void push(int value)
{
m_data.Push(value);
if (m_min.Count == 0 || value < m_min.Peek())
m_min.Push(value);
else
m_min.Push(m_min.Peek());
}
public void pop()
{
if (m_data.Count > 0 && m_min.Count > 0)
{
m_data.Pop();
m_min.Pop();
}
}
public int min()
{
Trace.Assert(m_data.Count > 0 && m_min.Count > 0, "");
return m_min.Peek();
}
#endregion
}
|
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
|
public class StackWithMin {
private Stack<Integer> m_data;
private Stack<Integer> m_min;
public void push(int value) {
m_data.push(value);
if (m_min.size() == 0 || value < m_min.peek())
m_min.push(value);
else
m_min.push(m_min.peek());
}
public int pop() {
assert m_data.size() > 0 && m_min.size() > 0 : "";
int value = m_data.pop();
m_min.pop();
return value;
}
public int min() {
assert m_data.size() > 0 && m_min.size() > 0 : "";
return m_min.peek();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
} |
Python实现方式：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class StackWithMin(object):
def __init__(self):
self._m_data = []
self._m_min = []
def push(self, value):
self._m_data.append(value)
if len(self._m_min) == 0 or value < self._m_min[-1]:
self._m_min.append(value)
else:
self._m_min.append(self._m_min[-1])
def pop(self):
assert len(self._m_min) > 0 and len(self._m_data) > 0
value = self._m_data[-1]
self._m_data = self._m_data[:-1]
self._m_min = self._m_min[:-1]
return value
def min(self):
assert len(self._m_min) > 0 and len(self._m_data) > 0
return self._m_min[-1]
|