算法

min stack

题目

设计一个Stack，实现如下操作：

  1. push(), 入栈
  2. pop(), 出栈
  3. top(), 返回栈顶元素
  4. getMin(), 返回栈中的最小元素

注意上面的操作，都要在常数时间完成。

分析

Leetcode上面的原题，思路并不难想，但是AC还是有难度的，尤其是用Java，如果能够确保不出现MLE？我们先逐步分析一下。

首先，第一个思路，最容易想到，定义一个新的栈，栈的每一个元素包含两个数，一个当前数，一个入栈到目前为止的最小数。有如下的代码示例：

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
class Element {
    public int x;
    public int min;
    public Element(int x, int min) {
        super();
        this.x = x;
        this.min = min;
    }
}
public class MinStackSlow {
    
    private LinkedList<Element> stack = new LinkedList<Element>();
    
    public void push(int x) {
        int min = x;
        if (!stack.isEmpty() && stack.getFirst().min < min) 
            min = stack.getFirst().min;
        stack.addFirst(new Element(x, min));
    }
    public void pop() {
        stack.removeFirst();
    }
    public int top() {
        Element el = stack.getFirst();
        return el.x;
    }
    public int getMin() {
        return stack.getFirst().min;
    }
}

代码很简单，但是MLE，内存超了。。。很不幸。那么如何优化呢？其实我们自己走一走这个过程，就会发现，在入栈出栈，以及getMin的过程中，有一些值，是不会出现在getMin中的。有一些min的数都是一样的。

那么我们浪费了空间来存储这些一样的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
44
45
46
47
48
49
class MinElement {
    public int min;
    public int freq;
    public MinElement(int min, int freq) {
        this.min = min;
        this.freq = freq;
    }
}
public class MinStack {
    
    private LinkedList<Integer> stack = new LinkedList<Integer>();
    private LinkedList<MinElement> min = new LinkedList<MinElement>();
    
    public void push(int x) {
        if (min.isEmpty()) {
            min.addFirst(new MinElement(x, 1));
        } else {
            if (x == min.getFirst().min) {
                min.getFirst().freq += 1;
            } else if (x <  min.getFirst().min) {
                min.addFirst(new MinElement(x, 1));
            }
        }
        stack.addFirst(x);
    }
    public void pop() {
        int top = stack.removeFirst();
        if (top == min.getFirst().min) {
            if (min.getFirst().freq == 1) {
                min.removeFirst();
            } else {
                min.getFirst().freq -= 1;
            }
        }
    }
    public int top() {
        return stack.getFirst();
    }
    public int getMin() {
        return min.getFirst().min;
    }
}

提交之后，你会发现，代码还是有问题，人就是内存不过关，还能怎么优化呢？难道是LinkedList的问题？实际上，还真是这个问题。Java中LinkedList是一个双向的链表，实际上我们实现一个栈，只需要单向的。我们自己实现栈试试。代码比较糙，有些实现也不合规范。
但意思没问题，如下：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package leetcode.min.stack;
class IntNode {
    public int x;
    public IntNode next;
    public IntNode(int x, IntNode next) {
        this.x = x;
        this.next = next;
    }
}
class IntStack {
    private IntNode head;
    public void push(int x) {
        if (null == head) {
            head = new IntNode(x, null);
        } else {
            IntNode newHead = new IntNode(x, head);
            head = newHead;
        }
    }
    public void pop() {
        head = head.next;
    }
    public int top() {
        return head.x;
    }
}
class PairNode {
    public int min;
    public int freq;
    public PairNode next;
    public PairNode(int min, int freq, PairNode next) {
        super();
        this.min = min;
        this.freq = freq;
        this.next = next;
    }
}
class PairStack {
    private PairNode head;
    public void push(int x) {
        if (null == head) {
            head = new PairNode(x, 1, null);
        } else {
            if (x == head.min) {
                head.freq += 1;
            } else if (x < head.min) {
                PairNode newHead = new PairNode(x, 1, head);
                head = newHead;
            }
        }
    }
    public void pop(int x) {
        if (x == head.min) {
            if (head.freq > 1) {
                head.freq -= 1;
            } else {
                head = head.next;
            }
        }
    }
    public int top() {
        return head.min;
    }
}
public class SmallMemoryStack {
    private IntStack stack = new IntStack();
    private PairStack min = new PairStack();
    public void push(int x) {
        stack.push(x);
        min.push(x);
    }
    public void pop() {
        min.pop(stack.top());
        stack.pop();
    }
    public int top() {
        return stack.top();
    }
    public int getMin() {
        return min.top();
    }
}

通过了，看来问题确实如此。这也给了我们一个提醒，在实际的编码中，需要考虑的不仅仅是功能的实现，还有效率上的考虑。我们往往优先考虑时间，大多数时间考虑时间。但，空间也是同样重要的，尤其是Java这样的语言。

【完】