来源：LeetCode
难度：简单
描述：
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
示例1：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.
分析：
这是一道数据结构设计题，其实就是让我们对栈增加返回最小值的功能。
由于题目要求push、pop和min操作的时间复杂度必须为O(1)，因此我们不能在需要最小值的时候，再做排序、查找等操作来获取。
对于O(1)，最常见的肯定是空间换时间的方法，提前将最小值存储下来，使用的时候直接返回。此处介绍两种方法，如下
解题
方法一：双栈法
思路：
采用两个栈，一个栈正常存放元素，另一个栈存放当前元素的最小值，和上一个栈中的元素一一对应
元素入栈时，主栈直接入栈，小栈需比较当前入栈元素和小栈栈顶元素那个小，再次入栈较小的那个元素即可，出栈时主栈和小栈同时出栈，获取当前栈的最小值即是小栈的栈顶
代码：
1Stack<Integer> masterStack;
2Stack<Integer> minStack;
3
4public MinStack() {
5 masterStack = new Stack<>();
6 minStack = new Stack<>();
7}
8
9public void push(int x) {
10 //主栈直接入栈元素
11 masterStack.push(x);
12
13 //小栈为空时 直接入栈
14 if (minStack.isEmpty()) {
15 minStack.push(x);
16 } else {
17 //不为空，当前元素与小栈栈顶元素进行比较 入栈较小的那个
18 minStack.push(Math.min(minStack.peek(), x));
19 }
20}
21
22public void pop() {
23 //同时出栈
24 masterStack.pop();
25 minStack.pop();
26}
27
28public int top() {
29 return masterStack.peek();
30}
31
32public int getMin() {
33 //最小元素就是小栈栈顶元素
34 return minStack.peek();
35}方法二：单栈法
思路：
方法一额外用了一个辅助栈来存储最小元素，其实用一个栈也可以实现
入栈时，先判断栈顶元素和待入栈元素大小，用临时变量记录较小的那个，再将待入栈元素入栈，并将临时变量记录的小元素也入栈
出栈时，需连续出两次，因为入栈时将元素和最小值同时入栈了
最小值即是栈顶元素
本方法相当于将方法一中的最小栈和主栈融合到一起了
代码：
1Stack<Integer> masterStack;
2
3public MinStack() {
4 masterStack = new Stack<>();
5}
6
7public void push(int x) {
8
9 //为空直接入两次即可
10 if (masterStack.isEmpty()) {
11 masterStack.push(x);
12 masterStack.push(x);
13 } else {
14 //不为空，记录栈顶和当前元素较小的那个，先入当前元素，再入较小的那个
15 int temp = Math.min(masterStack.peek(), x);
16 masterStack.push(x);
17 masterStack.push(temp);
18 }
19}
20
21public void pop() {
22 //出栈两次
23 masterStack.pop();
24 masterStack.pop();
25}
26
27public int top() {
28 //实际元素在栈顶的下一个位置，因此出栈栈顶最小值
29 // 记录真实元素后，再将最小值入栈，返回真实元素即可
30 int min = masterStack.pop();
31 int real = masterStack.peek();
32 masterStack.push(min);
33 return real;
34}
35
36public int getMin() {
37 //最小元素就是小栈栈顶元素
38 return masterStack.peek();
39}
以上仅是个人思路解法
转载请注明：XAMPP中文组官网 » 经典面试题34_栈的最小值解法思路