java剑指offer30:包含min函数的栈

欢迎关注公众号:

java剑指offer30:包含min函数的栈

 

题目描述:

java剑指offer30:包含min函数的栈

java剑指offer30:包含min函数的栈

思路分析:

解法一:利用辅助栈

方法一的基本思想是利用两个栈来实现数据的入栈和栈,一个栈保存原始数据,另一个栈保存所有入栈的数据的最小值,这样,查询最小值时只要返回最小值栈的栈顶元素即可。具体实现借用牛客网的答案:

  • 首先初始化原始栈stack 和最小值栈stack_min(存储每次跟原栈中元素比较后的最小元素)

    java剑指offer30:包含min函数的栈

  • 接下来插入(push) ‘1’这个元素,此时两个栈的变化如下图:

    java剑指offer30:包含min函数的栈

  • 然后再插入(push) ‘2’这个元素,此时两个栈又变化如下图

    java剑指offer30:包含min函数的栈

  • 接着要获取栈顶元素,如下图:

    java剑指offer30:包含min函数的栈

  • 接着再次插入第三个元素 ‘1’,两个栈又发生如下变化

    java剑指offer30:包含min函数的栈

  • 最后再次利用top函数获取到栈顶元素就变成了 1,调用min函数则获取最小值依然是 -1。

    java剑指offer30:包含min函数的栈

实现过程整体如下图所示:

java剑指offer30:包含min函数的栈

实现代码如下所示:

package JavaOffer;
/*
 * @project project
 * @author liyongping
 * @creed: just do it
 * @ date 2021/12/15 12:34
 * @ version 1.0
 */
​
import java.util.Stack;
​
public class JavaOffer30 {
    private Stack<Integer> dataStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
​
    public static void main(String[] args) {
           JavaOffer30  jo30=new JavaOffer30();
           jo30.push(1);
           jo30.push(2);
           jo30.push(3);
           jo30.push(4);
        System.out.println(jo30.min());
        System.out.println(jo30.top());
​
    }
    public void push(int node) {
        dataStack.push(node);
        minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
    }
​
    public void pop() {
        dataStack.pop();
        minStack.pop();
    }
​
    public int top() {
        return dataStack.peek();
    }
​
    public int min() {
        return minStack.peek();
    }
}
​

上述代码运行结果如下,返回最小值和栈顶元素:

java剑指offer30:包含min函数的栈

解法二:暴力算法

由于没有看清题解,以为用一个栈就可以实现在栈中查最小值的算法,min函数遍历栈,取出栈中最小值的元素即可,这种算法破环了栈中数据的完整性,通过弹出栈中元素比较的方法来获取最小值,并不可行,不满足题目复杂度的要求且破坏了站的结构。实现代码如下:

package JavaOffer;/*
 * @project project
 * @author liyongping
 * @creed: just do it
 * @ date 2021/12/15 12:34
 * @ version 1.0
 */
​
import java.util.Stack;
​
public class JavaOffer30 {
    Stack<Integer> stack =new Stack <Integer>();
​
    public static void main(String[] args) {
           JavaOffer30  jo30=new JavaOffer30();
           jo30.push(1);
           jo30.push(2);
           jo30.push(3);
           jo30.push(4);
        System.out.println(jo30.min());
​
    }
​
    public void push(int node) {
         stack.push(node);
    }
​
    public void pop() {
       if(!stack.isEmpty()){
           stack.pop();
       }
    }
    public int top() {
        return stack.peek();
    }
​
    public int min() {
        int min=stack.pop();
        while (!stack.isEmpty()){
            if(min>stack.peek()){
                min=stack.peek();
                stack.pop();
            }
        }
        return min;
    }
​
}
​

 上述代码运行结果为:

java剑指offer30:包含min函数的栈

 

上一篇:左值引用与右值引用


下一篇:20.有效的括号