437，剑指 Offer-包含min函数的栈

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #剑指offer 34个

The best way out is always through.

最好的出路永远都是勇往直前。

问题描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

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

提示：

各函数的调用总次数不超过 20000 次

使用辅助类解决

这道题让我们自定义一个栈，有push，pop，top，min四个函数。这题和官方的Stack相比就多了一个min函数。栈的实现我们可以使用链表，先来定义一个链表类

 1class ListNode {
 2    public int val;
 3    public int min;//最小值
 4    public ListNode next;
 5
 6    public ListNode(int val, int min, ListNode next) {
 7        this.val = val;
 8        this.min = min;
 9        this.next = next;
10    }
11}

这里对链表的操作永远都是链表的头，假如往栈中加入3→2→5→4，画个图来看一下使用链表怎么操作的

代码比较简单，来看下

 1class MinStack {
 2    //链表头，相当于栈顶
 3    private ListNode head;
 4
 5    //压栈，需要判断栈是否为空
 6    public void push(int x) {
 7        if (empty())
 8            head = new ListNode(x, x, null);
 9        else
10            head = new ListNode(x, Math.min(x, head.min), head);
11    }
12
13    //出栈，相当于把链表头删除
14    public void pop() {
15        if (empty())
16            throw new IllegalStateException("栈为空……");
17        head = head.next;
18    }
19
20    //栈顶的值也就是链表头的值
21    public int top() {
22        if (empty())
23            throw new IllegalStateException("栈为空……");
24        return head.val;
25    }
26
27    //链表中头结点保存的是整个链表最小的值，所以返回head.min也就是
28    //相当于返回栈中最小的值
29    public int min() {
30        if (empty())
31            throw new IllegalStateException("栈为空……");
32        return head.min;
33    }
34
35    //判断栈是否为空
36    private boolean empty() {
37        return head == null;
38    }
39}

上面解决方式是使用一个辅助的类，实际上如果使用辅助类，我们也可以使用官方提供的栈，像下面这样。

 1class MinStack {
 2    private Stack<StackNode> stack = new Stack<>();
 3
 4    //压栈
 5    public void push(int x) {
 6        if (empty()) {
 7            stack.push(new StackNode(x, x));
 8        } else {
 9            stack.push(new StackNode(x, Math.min(x, min())));
10        }
11    }
12
13    //出栈
14    public void pop() {
15        if (empty())
16            throw new IllegalStateException("栈为空……");
17        stack.pop();
18    }
19
20    public int top() {
21        if (empty())
22            throw new IllegalStateException("栈为空……");
23        return stack.peek().val;
24    }
25
26    public int min() {
27        if (empty())
28            throw new IllegalStateException("栈为空……");
29        return stack.peek().min;
30    }
31
32    //判断栈是否为空
33    private boolean empty() {
34        return stack.isEmpty();
35    }
36}
37
38class StackNode {
39    public int val;
40    public int min;
41
42    public StackNode(int val, int min) {
43        this.val = val;
44        this.min = min;
45    }
46}

使用单个栈解决

也可以使用官方提供的栈，当压栈的值小于栈中最小值时，先把最小值入栈，然后再把需要压栈的值入栈，最后再更新栈中最小值。如果压栈的值大于栈中最小值的时候，直接压栈，这里就以[6，2，1，4]分别入栈来看一下

这是压栈的过程，出栈的时候如果出栈的值等于最小值，说明最小值已经出栈了，要更新最小值，估计直接看代码会更明白一些

 1class MinStack {//push方法可能会加入很多min
 2    int min = Integer.MAX_VALUE;
 3    Stack<Integer> stack = new Stack<>();
 4
 5    public void push(int x) {
 6        //如果加入的值小于最小值，要更新最小值
 7        if (x <= min) {
 8            stack.push(min);
 9            min = x;
10        }
11        stack.push(x);
12    }
13
14    public void pop() {
15        //如果把最小值出栈了，就更新最小值
16        if (stack.pop() == min)
17            min = stack.pop();
18    }
19
20    public int top() {
21        return stack.peek();
22    }
23
24    public int min() {
25        return min;
26    }
27}

这种方式虽然也能解决，但如果压栈的值一直递减的话，栈中会压入很多的min，实际上我们还可以在改一下，栈中压入的是需要压栈的值和最小值的差值，这样就不会压入min了，看下代码

 1public class MinStack {
 2    long min;
 3    Stack<Long> stack = new Stack<>();
 4
 5    public void push(int x) {
 6        if (stack.isEmpty()) {
 7            stack.push(0L);
 8            min = x;
 9        } else {
10            //这里入栈的是入栈的值和最小值的差值，有可能为负，也有可能为正。
11            stack.push(x - min);
12            if (x < min)
13                min = x;
14        }
15    }
16
17    public void pop() {
18        if (stack.isEmpty())
19            return;
20        long pop = stack.pop();
21        //因为入栈的是差值，当出栈的为负数的时候，说明栈中最小值已经出栈了，
22        //这里要重新更新最小值
23        if (pop < 0)
24            min -= pop;
25    }
26
27    public int top() {
28        long top = stack.peek();
29        if (top > 0) {
30            //栈顶元素如果是正的，说明栈顶元素压栈的时候是比栈中最小值大的，根据
31            //top=x - min，可以计算x=top+min
32            return (int) (top + min);
33        } else {
34            //当栈顶元素是负数的时候，说明栈顶元素压栈的时候是比栈中最小值小的，
35            //而压栈完之后他会更新最小值min，所以如果在使用上面公式肯定是不行
36            //的。如果栈顶元素压栈的时候比最小值小，他会更新最小值，这个最小值
37            //就是我们要压栈的值，所以这里直接返回min就行了。
38            return (int) (min);
39        }
40    }
41
42    public int min() {
43        return (int) min;
44    }
45}

使用双栈解决

这个代码比较简洁，就不在说了，直接看下代码

 1class MinStack {
 2    //栈1存放的是需要压栈的值
 3    Stack<Integer> stack1 = new Stack<>();
 4    //栈2存放的是最小值
 5    Stack<Integer> stack2 = new Stack<>();
 6
 7    public void push(int x) {
 8        stack1.push(x);
 9        if (stack2.empty() || x <= min())
10            stack2.push(x);
11    }
12
13    public void pop() {
14        //如果出栈的值等于最小值，说明栈中的最小值
15        //已经出栈了，因为stack2中的栈顶元素存放的
16        //就是最小值，所以stack2栈顶元素也要出栈
17        if (stack1.pop() == min())
18            stack2.pop();
19    }
20
21    public int top() {
22        return stack1.peek();
23    }
24
25    public int min() {
26        return stack2.peek();
27    }
28}