力扣155.最小栈 & 剑指offer 20.包含min 函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

思路：

    1. 定义两个栈，一个 stack1 栈用于存储栈的元素，另一个 stack2 栈用来存储当前stack1的栈顶元素对应的最小的元素，构造函数stack2压入一个Integer.MAX_VALUE
    2. 每当push 一个元素，把当前元素和栈2的栈顶元素比较，把较小者压入栈2，需要存储的元素压入栈一，这样两个栈的栈顶元素分别是我们存储的值和当前的最小值
    3. 每当pop 一个元素，同时pop stack2 中的一个元素

　4. top()函数返回stack的栈顶值，min()函数返回 stack2 的栈顶值

 1 class MinStack {
 2     Stack<Integer> stack1 = new Stack<Integer>();
 3     Stack<Integer> stack2 = new Stack<Integer>();
 4     // int min = Integer.MAX_VALUE;
 5 
 6     /** initialize your data structure here. */
 7     public MinStack() {
 8         stack2.push(Integer.MAX_VALUE); // 把int类型的最大值压入栈2
 9     }
10     
11     public void push(int x) {
12         // 把当前元素和栈2的栈顶元素比较，把较小者压入栈2， 需要存储的元素压入栈一
13         int min = Math.min(x, stack2.peek());
14        
15         stack1.push(x);
16         stack2.push(min);
17     }
18     
19     public void pop() {
20         // 出栈的时候两个栈同时出栈
21         if(!stack1.empty()){
22             stack1.pop();
23             stack2.pop();
24         }
25     }
26     
27     public int top() {
28         if(!stack1.empty()){
29             return stack1.peek();
30         }
31         return 0;
32     }
33     
34     public int getMin() {
35         if(!stack2.empty()){
36             return stack2.peek();
37         }
38         return 0;
39     }
40 }

力扣测试时间为9ms，空间为41.4MB

复杂度分析：

时间复杂度：获取最小值的时间复杂度为O(1)

空间复杂度：需要两个栈，所以空间复杂度为O(n)