如何设计一个具有getMaxValue和getMinValue的栈

题目补充

如何设计一个具有getMaxValue和getMinValue的栈，并且成员方法时间复杂度都为O(1)?

实现方法

这是一道招商证券的面试题，这里我们借助JDK提供的动态数组ArrayList实现，首先定义接口

package com.webos.blog;

/**
 * Create by yang 2020-04-16 21:46
 */
public interface Stack {
    void push(int num);
    int pop();
    int getMaxValue();
    int getMinValue();
    boolean isEmpty();
    int getSize();
}

实现

package com.webos.blog;

import java.util.ArrayList;
import java.util.List;

/**
 * Create by yang 2020-04-16 21:47
 */
public class StackImpl implements Stack {
    private List<Integer> data;
    private List<Integer> maxValueData;
    private List<Integer> minValueData;
    private Integer maxValue =null;
    private Integer minValue =null;

    public  StackImpl(int capacity){
        if(capacity<1){
            throw new IllegalArgumentException("illegal capcity");
        }
        data = new ArrayList<>(capacity);
        maxValueData = new ArrayList<>();
        minValueData = new ArrayList<>();
    }

    @Override
    public void push(int num) {
        data.add(num);
        if(maxValue==null||num>maxValue){
            maxValue = num;
        }
        //如果num<=maxValue 则maxValue重复入栈一次,确保pop正常
        maxValueData.add(maxValue);

        if(minValue==null||num<minValue){
            minValue = num;
        }
        //如果num>=minValue 则minValue重复入栈一次,确保pop正常
        minValueData.add(minValue);
    }

    @Override
    public int pop() {
        if(isEmpty()){
            throw new RuntimeException("stack is empty!");
        }
        minValueData.remove(minValueData.size()-1);
        maxValueData.remove(maxValueData.size()-1);

        minValue = minValueData.get(minValueData.size() - 1);
        maxValue = maxValueData.get(maxValueData.size()-1);
        return data.remove(getSize() - 1);
    }

    @Override
    public int getSize(){
        return data.size();
    }

    @Override
    public int getMaxValue() {
        return maxValue;
    }

    @Override
    public int getMinValue() {
        return minValue;
    }

    @Override
    public boolean isEmpty() {
        return data.isEmpty();
    }

    @Override
    public String toString() {
        StringBuilder sbu = new StringBuilder();
        sbu.append("data:[");
        for (int i = 0; i < data.size(); i++) {
            sbu.append(data.get(i));
            if(i!=data.size()-1){
                sbu.append(",");
            }
        }
        sbu.append("]\n");
        sbu.append("maxValue=").append(getMaxValue()).
                append("\nminValue=").append(getMinValue());
        return sbu.toString();
    }
}

测试代码

package com.webos.blog;

/**
 * Create by yang 2020-04-16 21:50
 */
public class Test4 {
    public static void main(String[] args) {
        StackImpl stack = new StackImpl(10);
        stack.push(10);
        stack.push(2);
        stack.push(1);
        stack.push(30000);

        stack.push(500);
        stack.push(6000);
        stack.push(89);

        System.out.println(stack);
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println("=====================");
        System.out.println(stack);
    }
}

输出结果

data:[10,2,1,30000,500,6000,89]
maxValue=30000
minValue=1
=====================
data:[10,2,1]
maxValue=10
minValue=1