获取最小值栈——优化

客官°小女子只卖身不卖艺 2022-02-21 15:21 200阅读 0赞

**题目：**  
我现在需要实现一个栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值，你会怎么做呢？你可以假设栈里面存的都是int整数。

**思路**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]

**实现**

import java.util.ArrayList;
    import java.util.List;
    
    public class 获取最小值栈 {
    	private List<Integer> data = new ArrayList<Integer>();
    	private List<Integer> mins = new ArrayList<Integer>();
    	
    	public void push(int num){
    		data.add(num);
    		if(mins.size() == 0){
    			//初始化mins
    			mins.add(num);
    		}else{
    			//辅助栈mins每次push当时最小值
    			int min = getMin();
    			if(num >= min){
    				mins.add(min);
    			}else{
    				mins.add(num);
    			}
    		}
    	}
    	
    	public int pop(){
    		//栈空，异常返回-1
    		if(data.size() == 0){
    			return -1;
    		}
    		//pop时两栈同步pop
    		mins.remove(mins.size()-1);
    		return data.remove(data.size()-1);
    	}
    	
    	public int getMin(){
    		//栈空异常返回-1
    		if(mins.size() == 0){
    			return -1;
    		}
    		//返回栈顶元素
    		return mins.get(mins.size()-1);
    	}
    }

**改进**

1.  异常处理有点问题，当栈内为空的时候，你返回-1，但是如果用户push过-1，  
    那么你返回-1的时候，是用户push进来的值，还是栈为空，就不得而知了。  
    2.如果依次入栈是【2，1，2，3，4，5，6】  
    那么辅助栈和入栈的栈为  
    ![在这里插入图片描述][20190411095353683.png]  
    优化：  
    1.加抛异常  
    2.改为索引进辅助栈  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
    **实现**

package 最小值栈;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class 优化获取最小值栈 {
    	/*
    	 * 辅助栈里存索引，避免重复
    	 */
    	private List<Integer> data = new ArrayList<Integer>();
    	private List<Integer> mins = new ArrayList<Integer>();
    	
    	public void push(int num) throws Exception{
    		data.add(num);
    		if(mins.size() == 0){
    			//初始化mins
    			mins.add(0);
    		}else{
    			//辅助栈mins push最小值的索引
    			int min = getMin();
    			if(num < min){
    				mins.add(data.size() - 1);
    			}
    		}
    	}
    	
    	public int pop() throws Exception{
    		//栈空 抛出异常
    		if(data.size() == 0){
    			throw new Exception("栈为空");
    		}
    		//pop时先获取索引
    		int popIndex = data.size() -1;
    		//获取mins栈顶元素，它是最小值索引
    		int minIndex = mins.get(mins.size() - 1);
    		//如果pop出去的索引时最小值索引，mins才出栈
    		if(popIndex == minIndex){
    			mins.remove(mins.size() - 1);
    		}
    		return data.remove(data.size() -1);
    	}
    	
    	public int getMin() throws Exception{
    		//栈空，抛出异常
    		if(data.size() == 0){
    			throw new Exception("栈为空");
    		}
    		//获取mins栈顶元素它是最小值索引
    		int minIndex = mins.get(mins.size() -1);
    		return data.get(minIndex);
    	}
    }

参考：[https://mp.weixin.qq.com/s/SFbGNAEGnqZMib9VMC26Ew][https_mp.weixin.qq.com_s_SFbGNAEGnqZMib9VMC26Ew]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220221/3d9fbc5c45b044a182461b3ecb5ae1f4.png
[20190411095353683.png]: /images/20220221/c6f364dbcd38474f9680de33d03fa474.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220221/e0b22bc1f31e4a71ab4b1e716b63564b.png
[https_mp.weixin.qq.com_s_SFbGNAEGnqZMib9VMC26Ew]: https://mp.weixin.qq.com/s/SFbGNAEGnqZMib9VMC26Ew