java 要求用时空复杂度O(1)求出栈（结构自定）中的最大最小值

古城微笑少年丶 2022-05-03 03:28 126阅读 0赞

package com.zhangheng;
    
    import java.util.Stack;
    
    /**
     * 栈的使用  高效求栈中的最大最小值 时空复杂度均是O(1)
     * @date 2018-10-26 
     * @author hengzhang2@iflytek.com
     *
     * @param <E>
     */
    public class SpecialStack<E extends Number> {
    	Stack<Long> stack = new Stack<Long>();
    	Stack<Long> stackMin = new Stack<Long>();// 存放求最小值的栈
    	Stack<Long> stackMax = new Stack<Long>();// 存放求最大值的栈
    
    	public void push(Long l) {
    		stack.push(l);
    
    		if(stackMin.isEmpty()){
    			stackMin.push(l);
    		}else{
    			if(l.longValue() <= stackMin.peek()){
    				stackMin.push(l);
    			}
    		}
    		
    		
    		if(stackMax.isEmpty()){
    			stackMax.push(l);
    		}else{
    			if(l.longValue() > stackMax.peek()){
    				stackMax.push(l);
    			}
    		}
    		
    	}
    
    	public Long pop()// 一定要记着，非空才能pop()
    	{
    		if (!stack.isEmpty() && !stackMin.isEmpty() && !stackMax.isEmpty()) {
    			Long e = stack.pop();
    			stackMin.pop();
    			stackMax.pop();
    			return e;
    		} else {
    			System.out.println("栈为空了");
    			return null;
    		}
    
    	}
    
    	public Long getMin() {
    		return stackMin.peek();
    	}
    
    	public Long getMax() {
    		return stackMax.peek();
    	}
    
    	
    	public static void main(String[] args) {
    		SpecialStack<Long> spect = new SpecialStack<Long>();
    		spect.push(2l);
    		spect.push(1l);
    		spect.push(4l);
    		spect.push(7l);
    		spect.push(5l);
    		
    		
    		System.out.println("spect.stack1="+spect.stack);
    		System.out.println("spect.stackMin="+spect.stackMin);
    		System.out.println("spect.getMin()="+spect.getMin());
    		System.out.println("spect.stackMax="+spect.stackMax);
    		System.out.println("spect.getMax()="+spect.getMax());
    	}
    }

输出结果：  
spect.stack1=\[2, 1, 4, 7, 5\]  
spect.stackMin=\[2, 1\]  
spect.getMin()=1  
spect.stackMax=\[2, 4, 7\]  
spect.getMax()=7