剑指offer-包含min函数的栈

题目描述

• 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
• 地址： 牛客地址

解题方法

• 用两个栈实现该功能，dataStack用于存储数据，minStack用于栈顶维持数组最小值
• 当入栈时，dataStack正常入栈，minStack只有为空或者当前元素小于等于栈顶元素时才将当前元素入栈
• 当出栈时，dataStack正常出栈，只有当前出栈元素等于minStack栈顶元素时，minStack才出栈
• 获取最小值，便返回minStack的栈顶元素

经验教训

• 如何用基本的数据结构设计一个带有特殊功能的数据结构是面试中常考的点
• 注意出现重复元素时的处理（入栈时满足小于等于）

代码实现

import java.util.Stack;

public class Solution {
    Stack<Integer> dataStack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int node) {
        dataStack.push(node);
        //只有min栈为空或者当前元素小于等于min栈栈顶元素时，才将当前元素入栈
        if (minStack.empty() || node <= minStack.peek()) {
            minStack.push(node);
        }
    }

    public void pop() {
        //只有当前出栈元素等于min栈栈顶元素时，才出栈
        if (minStack.peek() == dataStack.pop()) {
            minStack.pop();
        }
    }

    public int top() {
        return dataStack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}