20 图解剑指Offer 包含min函数的栈 Java题解

忘是亡心i 2023-02-20 13:54 12阅读 0赞

### 20 图解剑指Offer 包含min函数的栈 Java题解 ###

*  20 图解剑指Offer 包含min函数的栈 Java题解
 *   *   *  题目链接
         *  题目描述
         *  题解:
         *  图解:
         *  代码:
         *  复杂度

# 20 图解剑指Offer 包含min函数的栈 Java题解 #

### [题目链接][Link 1] ###

### 题目描述 ###

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。  
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

### 题解: ###

1.主要实现push方法，stack1用来正常push元素，stack2只放最小元素。  
2.stack1push元素后: (1)当stack2为null时，stack2也push该元素。  
（2）stack2不为null时，如果该元素比stack2的栈顶元素小或相等，stack2添加该元素，否则stack2添加自己的栈顶元素。以上操作可保证stack2栈顶元素是最小元素。

### 图解: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]

### 代码: ###

import java.util.Stack;
    
    public class Solution { 
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        public void push(int node) { 
            stack1.push(node);
            if(stack2.isEmpty()){ 
                stack2.push(node);
            }else if(node <=  (int)stack2.peek()) { 
                stack2.push(node);
            }else { 
                stack2.push(stack2.peek());
            }
        }
        
        public void pop() { 
            stack1.pop();
            stack2.pop();
        }
        
        public int top() { 
            return stack1.peek();
        }
        
        public int min() { 
            return stack2.peek();
        }
    }

### 复杂度 ###

空间复杂度: 空间复杂度为O(n)  
最坏时间复杂度: 时间复杂度 min方法:O(1)

[Link 1]: https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627214536424.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70