转载

剑指offer:包含min函数的栈(Java)

1.题目描述

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

2.思路

题目提供了一个Stack类让我们用,所以可以new一个该类的对象,这样栈的压栈、弹栈和返回顶部最大值的方法就可以直接调用Stack类的了。

问题的关键就是min函数,并且要求时间复杂度为O(1)。

可以再使用一个Stack对象,只要往栈中压入一个元素,就把该元素和目前栈中最小值元素进行比较,如果更小,就把压入的元素添加到记录最小值元素的栈中,否则就把记录最小值栈的栈顶元素再压一次。如果栈进行了弹栈操作,那么记录最小值元素的栈同样也进行弹栈操作即可,min函数就是将记录最小值元素的栈栈顶元素返回即可,但是不要弹出。

简单讲就是两个栈A栈记录数据,B栈记录A栈中的最小值,A栈加一个数,就比较一次,较小的加入B栈中,A栈取出一个数据,B栈也取出栈顶数据,保证两个栈的数据量相同,如果向获取A栈中的最小值,就获取B栈的栈顶元素。

3.Code

import java.util.Stack;

public class Solution {
    
    Stack<Integer> s = new Stack<>();    //调用Java自带的栈对象
    Stack<Integer> minStack = new Stack<>();    //在定义一个栈,用来存储当前s栈中的最小值
    int minValue = Integer.MAX_VALUE;    //定义一个变量,用来记录当前的最小值,初始值设为Integer的最大值。
    
    public void push(int node) {    //压栈方法
        s.push(node);    //直接调用s的push方法,将元素压入栈中。
        if(node < minValue){    //如果进栈的元素小于当前的最小值就把进栈元素的值赋值该minValue。
            minValue = node;    //赋值操作
        }
        minStack.push(minValue);    //将当前的最小值压入minStack栈中。
    }
    
    public void pop() {    //弹栈方法
        s.pop();    //直接调用s的pop方法
        minStack.pop();    //minStack也相应的弹出最顶的元素,保证minStack和s的元素数量一致。
    }
    
    public int top() {    //查询最顶部的元素
        return s.peek();    //直接调用s的peek方法
    }
    
    public int min() {    //获取当前s栈中的最小值
        return minStack.peek();    //直接将minStack的最顶部的元素返回即可。
    }
}
原文  https://segmentfault.com/a/1190000019871354
正文到此结束
Loading...