设计一个有getMin功能的栈－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
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
package live.every.day.ProgrammingDesign.CodingInterviewGuide.StackAndQueue;

import java.util.Stack;

/**
 * 设计一个有getMin功能的栈
 *
 * 【题目】
 * 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
 *
 * 【要求】
 * １、push、pop、getMin操作的时间复杂度都是O(1)。
 * ２、设计的栈类型可以使用现成的栈结构。
 *
 * 【难度】
 * 简单
 *
 * 【解答】
 * 在设计上我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，记为dataStack；另一个栈用于保存
 * 每一步的最小值，记为minStack。具体的实现方式有两种。
 *
 * 第二种设计方案如下。
 *
 * 压入数据规则：
 * 假设当前数据为num，先将其压入dataStack。然后判断minStack是否为空：
 * 如果为空，则num也压入minStack；
 * 如果不为空，则比较num和minStack的栈顶元素中哪一个更小：如果num更小或两者相等，则num也压入minStack；如果minStack中
 * 栈顶元素小，则把minStack的栈顶元素重复压入minStack，即在栈顶元素上再压入一个栈顶元素。
 *
 * 弹出数据规则：
 * 在dataStack中弹出数据，弹出的数据记为value；弹出minStack中的栈顶；返回value。
 * 很明显可以看出，压入与弹出规则是对应的。
 *
 * 查询当前栈中的最小值：
 * 由上文的压入数据规则和弹出数据规则可知，minStack始终记录着dataStack中的最小值，所以minStack的栈顶元素始终是当前
 * dataStack中的最小值。
 *
 * 方案二的代码实现如StackWithGetMin2类所示：
 *
 * 【点评】
 * 方案一和方案二其实都是用minStack栈保存着dataStack每一步的最小值。共同点是所有操作的时间复杂度都为O(1)、空间复杂度
 * 都为O(n)。区别是：方案一中minStack压入时稍省空间，但是弹出操作稍费时间；方案二中minStack压入时稍费空间，但是弹出操
 * 作稍省时间。
 *
 * @author Created by LiveEveryDay
 */

public class StackWithGetMin2 {

    private final Stack<Integer> dataStack;
    private final Stack<Integer> minStack;

    public StackWithGetMin2() {
        this.dataStack = new Stack<>();
        this.minStack = new Stack<>();
    }

    public void push(int num) {
        this.dataStack.push(num);
        if (this.minStack.isEmpty()) {
            this.minStack.push(num);
        } else if (num < this.getMin()) {
            this.minStack.push(num);
        } else {
            int min = this.minStack.peek();
            this.minStack.push(min);
        }
    }

    public int pop() {
        if (this.dataStack.isEmpty()) {
            throw new RuntimeException("Stack is empty.");
        }
        this.minStack.pop();
        return this.dataStack.pop();
    }

    public int getMin() {
        if (this.minStack.isEmpty()) {
            throw new RuntimeException("Stack is empty.");
        }
        return this.minStack.peek();
    }

    public static void main(String[] args) {
        StackWithGetMin2 stack = new StackWithGetMin2();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(2);
        stack.pop();
        System.out.printf("The min element in stack is: %d%n", stack.getMin());
    }

}

// ------ Output ------
/*
The min element in stack is: 1
*/