LeetCode第155题—最小栈

本次写的题目是最小栈，为LeetCode里面的题目，让我们来康康是如何解出这道题目的吧，各位尚没有思路的小伙伴可以跟随着博主的解题思路一步步来，感受一下😎

🌱分析阶段

在初看题目的时候我们要仔细看要求，并且可以对示例进行画图模拟一下过程，在模拟后，我们可以知道我们所要做到的是什么👇：

 我们要做到最小栈，只需要多创建一个栈，命名为minStack。

为什么要设计一个minStack来专门存放最小数？这是因为我们每一次放入数据的时候，都可以先与栈顶的元素比较，看看该数据是不是最小的，如果是最小，则放在minStack栈顶，这样子就能够保证minStack栈顶的元素每一次都是最小的，然后栈顶往下的元素依次是：第二小，第三小，第四小...

接下来的各个函数我们一个一个分析。

🍃push函数：在每次push的时候，都先比较一下。若minStack为空，则直接放入；若不为空，则先将push的元素与minStack的栈顶元素比较，比minStack的栈顶元素大的不放入，小于或者等于minStack的栈顶元素的，则push进栈的同时，也push进minStack。

🍃pop函数：如果要弹出元素，则要先看看该元素是不是最小元素→可以让stack的栈顶元素与minStack的栈顶元素比较，如果相等，则两个栈都要弹出栈顶元素，反之则直接弹出stack元素即可。

🍃top函数：这个函数直接使用stack.peek()函数即可。

🍃getMin函数：该函数直接peek出minStack的栈顶元素即可😎

上面便是全部分析过程了，接下来让我们到代码阶段。

---

🌱代码阶段

按照之前分析，我们先创建两个栈，然后再一个一个函数逐渐完成。

🍃push函数

该函数没有需要特别注意的地方，我们只需要按照之前分析的过程用代码执行出来即可。具体代码如下👇：

import java.util.*;
 
class MinStack {
    
    public Stack stack = new Stack<>();
    public Stack minStack = new Stack<>();
 
    public MinStack() {
 
    }
    
    public void push(int val) {
        if(minStack.empty()){
            minStack.push(val);
        }else{
            if(val<=minStack.peek()){
                minStack.push(val);
            }
        }
        stack.push(val);
    }
 
    //其他未写代码省略
}

---

🍃pop函数

在pop函数这里我们要注意，其中有一个比较stack的栈顶元素与minStack栈顶元素的过程，如果相等则两个栈都要弹出栈顶元素，反之则只弹出stack的栈顶元素。但是我们要注意一点：peek（）函数的返回类型是Integr类。Integer类有一个特性：在[-128~128）区间内的元素地址才相同。所以在比较两个栈的栈顶元素时，先创建两个int变量来接纳两个栈顶元素，然后让这两个变量对比。具体代码如下👇：

import java.util.*;
 
class MinStack {
    
    public Stack stack = new Stack<>();
    public Stack minStack = new Stack<>();
 
    public MinStack() {
 
    }
    
    public void push(int val) {
        if(minStack.empty()){
            minStack.push(val);
        }else{
            if(val<=minStack.peek()){
                minStack.push(val);
            }
        }
        stack.push(val);
    }
    
    public void pop() {
        int stackNum = stack.peek();
        int minStackNum = minStack.peek();
        if(stackNum==minStackNum){  //这里不能直接写成stack.peek()==minStack.peek()，原因是因为Integer在【-128~128）内的对象地址相同，范围外是不相等的
            stack.pop();
            minStack.pop();
        }else{
            stack.pop();
        }
    }
    
    //还未写的函数暂时省略
}

---

🍃top函数：

该函数没有什么特殊，只需要直接peek出stack的栈顶元素即可。具体代码如下👇：

import java.util.*;
 
class MinStack {
    
    public Stack stack = new Stack<>();
    public Stack minStack = new Stack<>();
 
    public MinStack() {
 
    }
    
    public void push(int val) {
        if(minStack.empty()){
            minStack.push(val);
        }else{
            if(val<=minStack.peek()){
                minStack.push(val);
            }
        }
        stack.push(val);
    }
    
    public void pop() {
        int stackNum = stack.peek();
        int minStackNum = minStack.peek();
        if(stackNum==minStackNum){  //这里不能直接写成stack.peek()==minStack.peek()，原因是因为Integer在【-128~128）内的对象地址相同，范围外是不相等的
            stack.pop();
            minStack.pop();
        }else{
            stack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
}

---

🍃getMin函数：

该函数没有什么特殊，只需要直接peek出minStack的栈顶元素即可。具体代码如下👇：

import java.util.*;
 
class MinStack {
    
    public Stack stack = new Stack<>();
    public Stack minStack = new Stack<>();
 
    public MinStack() {
 
    }
    
    public void push(int val) {
        if(minStack.empty()){
            minStack.push(val);
        }else{
            if(val<=minStack.peek()){
                minStack.push(val);
            }
        }
        stack.push(val);
    }
    
    public void pop() {
        int stackNum = stack.peek();
        int minStackNum = minStack.peek();
        if(stackNum==minStackNum){  //这里不能直接写成stack.peek()==minStack.peek()，原因是因为Integer在【-128~128）内的对象地址相同，范围外是不相等的
            stack.pop();
            minStack.pop();
        }else{
            stack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

以上，便是全部代码啦😎让我们来运行下逝逝吧~

nice😎✨