leetcode-155

155. Min Stack

Description

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:

1
2
3
4
5
6
7
8
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.

Analyse

设计一个支持以O(1)时间复杂度获取当前最小值的栈

第一种思路，使用两个栈，一个存数据，一个存当前最小值，这种方法写起来简单，但需要两个栈

1
2
3
4
5
6
data    min
3       3
2       2
1       1
4       1
1       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
32
class MinStack {
public:
    stack<int> data;
    stack<int> min;

    MinStack() {    }

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

    void pop() {
        data.pop();
        min.pop();
    }

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

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

以上的方法中最小值可能被重复存多次，造成内存的浪费，可以继续改进

1
2
3
4
5
6
data    min
3       3
2       2
1       1
4
1       1

修改MinStack的push和pop，减少minimal中的重复元素

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
class MinStack {
public:
    stack<int> data;
    stack<int> minimal;

    MinStack() {    }

    void push(int x) {
        data.push(x);

        if (minimal.empty() || minimal.top() >= x)
        {
            minimal.push(x);
        }
    }

    void pop() {
        if (!minimal.empty() && data.top() == minimal.top())
        {
            minimal.pop();
        }

        data.pop();
    }

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

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

第二种思路，使用一种数据结构同时存数据和最小值，只使用一个栈

1
2
3
4
class Item{
    int val;
    int 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
class MinStack {
public:
    class Item {
        public:
            Item(int v, int m): val(v), min(m) {}
            int val;
            int min;
    };

    stack<Item> data;

    MinStack() { }

    void push(int x) {
        data.push(Item(x, data.empty() ? x : min(x, data.top().min)));
    }

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

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

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

第三种思路，使用一个栈，val和min都存在这个栈中，通过某种方式区分（来自leetcode）
如果当前push的值x比min_val小，将之前的min_val压栈，再将x压栈

pop的时候先取出真正的数据t

这个数据等于min_val时，再top + pop一次，更新min_val，

这个数据不等于min_val时，MinStack中没有push之前的min_val，无需进行操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
data    MinStack    min_val
                    INT_MAX
3       INT_MAX     3           min_val
        3                       data

2       3           2           min_val
        2                       data

1       2           1           min_val
        1                       data

4       4           1           data

1       1           1           min_val
        1                       data
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
class MinStack {
public:
    MinStack() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);

        min_val = INT_MAX;
    }

    void push(int x) {
        if (x <= min_val){
            data.push(min_val);
            min_val = x;
        }
        data.push(x);
    }

    void pop() {
        int t = data.top();
        data.pop();
        if (t == min_val){
            min_val = data.top();
            data.pop();
        }
    }

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

    int getMin() {
        return min_val;
    }
private:
    int min_val;
    stack<int> data;
};