包含min函数的栈（含思路解答示意图）【剑指offer——JAVA实现】

【考点：规律】顺时针打印矩阵

题目描述

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

解题思路

准备两个存储空间，一个为数组，存放每次得到的值；另一个为栈，每次存放当前最小值。如下图所示：

于是，反向推理，每次取出元素时，数组元素减一（置空），栈的顶部元素出栈，即可得到当前的最小值。

代码提交

import java.util.Stack;
import java.util.Arrays;

public class Solution {
    private Integer[] elements = new Integer[10]; 
    private int min = Integer.MAX_VALUE;
    private Stack<Integer> minStack = new Stack<Integer>();
    private int size;
    
    public void push(int node) {
        ensureCapacity(size + 1);
        elements[size++] = node;
        if(node < min) {
            min = node;
            minStack.push(node);
        }else {
            //minStack中对应的每一次存取后当前最小值
            minStack.push(min);
        }
    }
    
    private void ensureCapacity(int size) {
        int len = elements.length;
        
        if(size > len) {
            int newLen = 2 * size;
            elements = Arrays.copyOf(elements, newLen);
        }
    }
    
    public void pop() {
        if(!empty())
            elements[--size] = (Integer)null;
        //去掉原来最小值
        minStack.pop();
        //获取当前最小值
        min = minStack.peek();
    }
    
    private boolean empty() {
        return size == 0;
    }
    
    public int top() {
        if(!empty())
            return elements[size - 1];
        else return (Integer)null;
    }
    
    public int min() {
        return min;
    }
}

更多算法解答请点击《剑指offer》66题JAVA代码算法实现全集