剑指Offer-包含min函数的栈

「爱情、让人受尽委屈。」 2022-02-27 11:56 214阅读 0赞

## 题目描述 ##

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

看到题目特别是模拟编辑器上的代码，给了四个空函数，一开始有点搞不清题意，到底是要做什么。这题想要你模拟出一个栈的push、pop以及能够获得栈的top和栈中最小值，**也就是说，你新建了一个栈，不调用java封装的栈函数，调用这四个函数也是实现相应的操作**。  
**最优解：因为本题要求时间复杂度为O(1)，所以一定不能使用循环等操作，这里可以使用一个辅助minStack栈来存储当前stack的最小值。**

> 需要注意的是，若当前输入值的node比minStack.peek()小时，minStack将node压入；当node大于minStack.peek()时，minStack也要压入一个值，需要压入当前stack的最小值，也就是minStack.peek()。压入这个值得好处是为了在pop时，minStack可以和stack同时pop，不需要考虑当前pop的是不是最小值，还需不需要找第二小的值来替换。

## 最优解 ##

import java.util.Stack;
    
    public class Solution {
        Stack<Integer> stack = new Stack<Integer>();
        Stack<Integer> minStack = new Stack<Integer>();
        public void push(int node) {
            stack.push(node);
            if(minStack.isEmpty() || node<minStack.peek())      
                minStack.push(node);
            else
                minStack.push(minStack.peek());
        }
        
        public void pop() {
            // 同时压出
            if(!stack.isEmpty()){
                stack.pop();
                minStack.pop();
            }
        }
        
        public int top() {
            if(!stack.isEmpty())
                return stack.peek();
            else
                return (Integer) null;
        }
        
        public int min() {
            if(!minStack.isEmpty())
                return minStack.peek();
            else
                return (Integer) null;
        }
    }