Sword to Offer-30 包含min函数的栈 ❀

17 Apr 2020 in Algorithm

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

解题思路：

1、对于数据栈dataStack建立一个最小值栈minStack记录其实时最小值；
2、dataStack添加一个新元素时：
（1）查看minStack是否为空，为空表明这是入dataStack栈的第一个元素，此时栈内最小值就是新元素，将其push到minStack；
（2）不为空的情况下，新元素与与minStack顶部元素对比，将其中较小的一个push入minStack栈。（顶部元素表示在新元素入栈前，dataStack栈内的最小值）；
3、dataStack出栈元素时，minStack也要出栈一个元素；
4、读取栈顶元素和读取最小值函数直接返回dataStack和minStack栈顶值即可。

问题图解：

AC代码：

// A Stack With Min Method

import java.util.Stack;

public class Solution {

    private Stack<Integer> dataStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
    
    public void push(int node) {
        dataStack.push(node);
        if (minStack.isEmpty()) {
            minStack.push(node);
        }
        else {
            // 新的最小值要么是原最小值，要么是新添加的值
            if (minStack.peek() < node) {
                minStack.push(minStack.peek());
            }
            else {
                minStack.push(node);
            }
        }
    }
    
    public void pop() {
        dataStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

补充说明：

• 这里是牛客编码链接