最小栈实现及优化

怼烎@ 2022-02-04 12:25 305阅读 0赞

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

*  push(x) -- 将元素 x 推入栈中。
 *  pop() -- 删除栈顶的元素。
 *  top() -- 获取栈顶元素。
 *  getMin() -- 检索栈中的最小元素。

> **示例:**
> 
>     MinStack minStack = new MinStack();
>     minStack.push(-2);
>     minStack.push(0);
>     minStack.push(-3);
>     minStack.getMin();   --> 返回 -3.
>     minStack.pop();
>     minStack.top();      --> 返回 0.
>     minStack.getMin();   --> 返回 -2.

`一、要求在常数时间内检索到最小元素的栈，首先想到的方法是用一个变量存储最小元素，当入栈时同步维护最小元素，但是删除栈顶元素时需要重新遍历一遍栈获取最小元素，代码如下：`

public class MinStack {
    	// 存储栈里面的值
    	private List<Integer> data;
    
    	// 定义一个值存储最小值
    	private Integer minValue;
    
    	public MinStack() {
    		// 初始化栈
    		data = new ArrayList<>();
    	}
    
    	/*
    	 * 入栈
    	 */
    	public void push(int x) {
    		// 入栈时处理最小值
    		if (minValue == null || minValue > x) {
    			minValue = x;
    		}
    
    		// 入栈
    		data.add(x);
    	}
    
    	/*
    	 * 删除栈顶的元素
    	 */
    	public void pop() throws Exception {
    		if (data.size() == 0) {
    			throw new Exception("栈为空！");
    		}
    
    		data.remove(data.size() - 1);
    
    		// 删除栈顶元素后需要重新获取最小值，获取最小值的方法是便利一遍数组，需要先重置最小值
    		minValue = null;
    
    		for (Integer integer : data) {
    			if (minValue == null || minValue > integer) {
    				minValue = integer;
    			}
    		}
    	}
    
    	/*
    	 * 获取栈顶元素
    	 */
    	public int top() throws Exception {
    		if (data.size() == 0) {
    			throw new Exception("栈为空！");
    		}
    
    		// 获取栈顶元素并返回
    		return data.get(data.size() - 1);
    	}
    
    	/*
    	 * 检索栈中的最小元素
    	 */
    	public int getMin() throws Exception {
    		if (minValue == null) {
    			throw new Exception("栈为空！");
    		}
    		return minValue;
    	}
    }

二、前面已经说明上述方法在Pop方法的时间复杂度是O（N），能否把pop的时间复杂度降低到O(1)?

此处新增一个辅助栈，存储一个元素入栈后的栈中的最小值。如下图所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70][]

代码如下：

public class MinStack {
    	// 存储栈里面的值
    	private List<Integer> datas;
    
    	// 存储最小值
    	private List<Integer> mins;
    
    	public MinStack() {
    		// 初始化栈
    		datas = new ArrayList<>();
    		mins = new ArrayList<>();
    	}
    
    	/*
    	 * 入栈
    	 */
    	public void push(int x) throws Exception {
    		// 如果最小值栈为空，直接把值存入其中
    		if (mins.size() == 0) {
    			mins.add(x);
    		} else {
    			int min = getMin();
    			if (x >= min) {
    				mins.add(min);
    			} else {
    				mins.add(x);
    			}
    		}
    
    		// 入栈
    		datas.add(x);
    	}
    
    	/*
    	 * 删除栈顶的元素
    	 */
    	public void pop() throws Exception {
    		// datas 和 mins 栈的长度应该是一样的
    		if (datas.size() == 0) {
    			throw new Exception("栈为空！");
    		}
    
    		// 删除栈顶元素时需要同步删除最小栈的值
    		mins.remove(mins.size() - 1);
    
    		// 删除栈顶元素
    		datas.remove(datas.size() - 1);
    	}
    
    	/*
    	 * 获取栈顶元素
    	 */
    	public int top() throws Exception {
    		if (datas.size() == 0) {
    			throw new Exception("栈为空！");
    		}
    
    		// 获取栈顶元素并返回
    		return datas.get(datas.size() - 1);
    	}
    
    	/*
    	 * 检索栈中的最小元素
    	 */
    	public int getMin() throws Exception {
    		// 栈空，异常，返回-1
    		if (mins.size() == 0) {
    			throw new Exception("栈为空！");
    		}
    		// 返回mins栈顶元素
    		return mins.get(mins.size() - 1);
    	}
    }

三、但是上述方法还存在一个问题，如果元素大部分是升序时就会存在一个空间浪费问题，如下例子：

![2019050719475014.png][]

可以对mins进行判断，入栈时如果比mins的栈顶元素还大，则不再mins中加入栈顶元素，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1][]

参考代码如下：

public class MinStack {
    	// 存储栈里面的值
    	private List<Integer> datas;
    
    	// 存储最小值
    	private List<Integer> mins;
    
    	public MinStack() {
    		// 初始化栈
    		datas = new ArrayList<>();
    		mins = new ArrayList<>();
    	}
    
    	/*
    	 * 入栈
    	 */
    	public void push(int x) throws Exception {
    		// 如果最小值栈为空，直接把值存入其中
    		if (mins.size() == 0) {
    			mins.add(x);
    		} else {
    			int min = getMin();
    
    			// 如果新值比getMin()小时才需要加入，此处必须有等号
    			if (x <= min) {
    				mins.add(x);
    			}
    		}
    
    		// 入栈
    		datas.add(x);
    	}
    
    	/*
    	 * 删除栈顶的元素
    	 */
    	public void pop() throws Exception {
    		if (datas.size() == 0) {
    			throw new Exception("栈为空！");
    		}
    
    		// 获得本次移除的元素
    		int data = datas.get(datas.size() - 1);
    
    		// 获得最小元素
    		int min = getMin();
    
    		// 如果本次移除的元素大于等于最小元素，则需要移除
    		if (data >= min) {
    			mins.remove(mins.size() - 1);
    		}
    
    		// 删除栈顶元素
    		datas.remove(datas.size() - 1);
    	}
    
    	/*
    	 * 获取栈顶元素
    	 */
    	public int top() throws Exception {
    		if (datas.size() == 0) {
    			throw new Exception("栈为空！");
    		}
    
    		// 获取栈顶元素并返回
    		return datas.get(datas.size() - 1);
    	}
    
    	/*
    	 * 检索栈中的最小元素
    	 */
    	public int getMin() throws Exception {
    		// 栈空，异常，返回-1
    		if (mins.size() == 0) {
    			throw new Exception("栈为空！");
    		}
    		// 返回mins栈顶元素
    		return mins.get(mins.size() - 1);
    	}
    }

四、上述方法还有一个问题，当入栈的元素全部相等时还是会存在空间浪费问题，如下示例：

如 2 1 1 1 1 依次入栈，mins和datas的值依次如下：

mins 2 1 1 1 1

datas 2 1 1 1 1

解决办法：mins中存最小值所在的索引而不是值

参考代码如下：

public class MinStack {
    	// 存储栈里面的值
    	private List<Integer> datas;
    
    	// 存储最小值
    	private List<Integer> mins;
    
    	public MinStack() {
    		// 初始化栈
    		datas = new ArrayList<>();
    		mins = new ArrayList<>();
    	}
    
    	/*
    	 * 入栈
    	 */
    	public void push(int x) throws Exception {
    		datas.add(x);
    		if (mins.size() == 0) {
    			// 初始化mins
    			mins.add(0);
    		} else {
    			// 辅助栈mins push最小值的索引
    			int min = getMin();
    			if (x < min) {
    				mins.add(datas.size() - 1);
    			}
    		}
    	}
    
    	/*
    	 * 删除栈顶的元素
    	 */
    	public void pop() throws Exception {
    		// 栈空，抛出异常
    		if (datas.size() == 0) {
    			throw new Exception("栈为空");
    		}
    		// pop时先获取索引
    		int popIndex = datas.size() - 1;
    
    		// 获取mins栈顶元素，它是最小值索引
    		int minIndex = mins.get(mins.size() - 1);
    
    		// 如果pop出去的索引就是最小值索引，mins才出栈
    		if (popIndex == minIndex) {
    			mins.remove(mins.size() - 1);
    		}
    
    		// 删除栈顶元素
    		datas.remove(datas.size() - 1);
    	}
    
    	/*
    	 * 获取栈顶元素
    	 */
    	public int top() throws Exception {
    		if (datas.size() == 0) {
    			throw new Exception("栈为空！");
    		}
    
    		// 获取栈顶元素并返回
    		return datas.get(datas.size() - 1);
    	}
    
    	/*
    	 * 检索栈中的最小元素
    	 */
    	public int getMin() throws Exception {
    		// 栈空，抛出异常
    		if (datas.size() == 0) {
    			throw new Exception("栈为空");
    		}
    		// 获取mins栈顶元素，它是最小值索引
    		int minIndex = mins.get(mins.size() - 1);
    		
    		return datas.get(minIndex);
    	}
    }

**优化：如果限制了输入的范围，**比如限制了数值范围在 \[-100000, 100000\]，还可以进一步的优化：

定义一个min存储最小值，栈里面存储元素与min的差值，第一个元素入栈时存储0.如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2][]

代码如下：

package com.Ycb.stack;
    
    import java.util.Stack;
    
    public class MinStack1 {
    	private Stack<Integer> stack = new Stack<Integer>();
    
    	private Integer min;
    
    	public MinStack1() {
    		stack = new Stack<>();
    		min = Integer.MAX_VALUE;
    	}
    
    	public void push(Integer x) {
    		if (stack.isEmpty()) {
    			min = x;
    			stack.push(0);
    		} else {
    			// 计算差值
    			int compare = x - min;
    			stack.push(compare);
    
    			// 如果差值小于0，显然x成为最小值，否则最小值不变
    			min = compare < 0 ? x : min;
    		}
    	}
    
    	public Integer top() {
    		if (stack.isEmpty()) {
    			return null;
    		}
    
    		if (stack.size() == 1) {
    			return min;
    		}
    
    		if (stack.peek() < 0) {
    			return min;
    		} else {
    			return stack.peek() + min;
    		}
    	}
    
    	public void pop() {
    		if (stack.isEmpty()) {
    			return;
    		}
    		int top = stack.peek();
    		min = top < 0 ? (min - top) : min;
    		stack.pop();
    	}
    
    	public int getMin() {
    		return min;
    	}
    }

仅个人学习记录

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70]: /images/20220204/144ccda329cd4bf1badd16c8bc9a5e26.png
[2019050719475014.png]: /images/20220204/a2390401527c45af875a0920fb05dd10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1]: /images/20220204/9002738c67014db68eb37e2145c1abff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2]: /images/20220204/ae6026d562c5400f9d7d776ff7cc6558.png