转载

剑指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

正文到此结束