Stack with max and min 查找栈中最大最小数

最新推荐文章于 2021-02-27 11:46:57 发布

shendezhuti

最新推荐文章于 2021-02-27 11:46:57 发布

阅读量1.2k

点赞数

分类专栏：算法与数据结构

本文链接：https://blog.csdn.net/shendezhuti/article/details/78328111

版权

算法与数据结构专栏收录该内容

27 篇文章

订阅专栏

本文介绍如何创建一个数据结构，该结构在支持栈的基本操作（push和pop）的同时，还能快速返回栈中的最大值和最小值。通过继承栈并额外维护两个辅助栈，分别用于记录当前的最大值和最小值，从而在常数时间内完成查找最大值和最小值的操作。在插入和删除元素时，通过对辅助栈的相应更新，可以确保最大值和最小值始终是最新的。文中还给出了具体的Java代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

国外algorithm 课后的一个小quiz：

Create a data structure that efficiently supports the stack operations (push and pop) and also a return-the-maximum and

a return-the-minimum operation. Assume the elements are reals numbers so that you can compare them.

创建一个能够有效支持栈操作（插入与弹出）和返回最大最小数的数据结构，假设元素是我们可以比较的数字。

我们的想法可以这样：

首先让我们创建的类继承stack（之后会重写push与pop方法），创建stack名为store，放所有的元素。类里再多创建两个stack，分别为maxStack和minStack，用于辅助判断的储存。

当element元素push插入到我们store堆前时，先进行判断，如果元素比minStack中pop出的元素小，那么把这个element push加入到minStack中。同理还要对元素进行是否比maxStack最大元素大进行判断并且进行相应的操作。事实上，我们要注意这个细节，maxStack和minStack里面的元素在这样的操作中已经有了一个排序，最值的就是最近加入的（这太神奇刺激简单了不是吗！）

当元素出store栈时，也进行判断，如果元素的值等于相应的最大最小值，就在maxStack和minStack中进行pop操作（之前已经说了，最大的就是最近加入的，这里就会很方便直接用pop操作去除最值）

之后我们再包装一下判断最大最小的方法为minValue 和maxValue 。代码就好了。

具体的Java代码如下：

public class FindMaxMin extends Stack{
	
	private Stack minStack;
	private Stack maxStack;
	private Stack store;

	public FindMaxMin (){
		minStack=new Stack();
		maxStack=new Stack();
		store =new Stack();
	}
	public void push(int value){
		
		if(value>=MaxValue()){ //note the sign "=";
			maxStack.push(value);
		}
		if(value<=MinValue()){
			minStack.push(value);
		}
		store.push(value);
		
	}
	public Integer pop(){
		
		int value=store.pop();
		if(value==MaxValue()){
			maxStack.pop();
		}
		if(value==MinValue()){
			minStack.pop();
		}
		return value;
	}
	
   public int MaxValue(){
	   if(maxStack.isEmpty()){
		   return Integer.MIN_VALUE;
	   }else{
		   return maxStack.peek();//return but not remove  the most recently added element
	   }
	   
   }
   public int MinValue(){
	   if(minStack.isEmpty()){
		   return Integer.MAX_VALUE;
	   }else{
		   return minStack.peek();
	   }
	   
   }
   
	  /**
	   * 本地测试
	   * @param args
	   */
   public static void main(String args[]){
	   FindMaxMin test=new FindMaxMin();
	   test.push(9);
	   test.pop();
	   test.push(5);
	   test.push(3);
	   test.push(7);
	   test.push(1);
	   test.pop();
	   System.out.println("the biggest is "+test.MaxValue()+" and the smallest is "+test.MinValue());

   }
   
}