LeetCode min-stack

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 - push(x) -- 将元素 x 推入栈中。 - pop() -- 删除栈顶的元素。 - top() -- 获取栈顶元素。 - getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

解答:

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
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}

void push(int x) {
data.push(x);
if (minVal.empty() || x <= minVal.top())
minVal.push(x);
}

void pop() {
if (minVal.top() == data.top())
minVal.pop();
data.pop();
}

int top() {
return data.top();
}

int getMin() {
return minVal.top();
}
private:
stack<int> minVal;
stack<int> data;
};

class MinStack {
public:
/** initialize your data structure here. */
stack<int> s;
MinStack() {}

void push(int x) {
if (s.empty())
{
s.push(x);
s.push(x);
}
else
{
int temp=s.top();
s.push(x);
x < temp ? s.push(x) : s.push(temp);
}
}

void pop() {
s.pop();
s.pop();
}

int top() {
int temp = s.top();
s.pop();
int top = s.top();
s.push(temp);
return top;
}

int getMin() {
return s.top();
}
};

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×