【算法】设计一个getMin功能的栈

前置

• 数据结构—栈与队列
• 算法题栈与队列
• 编程语言: 尽管采用的Java,但避免了Java的容器特性， 读者应该很容易翻译成自己的语言。

题目

设计一个支持入栈、出栈、顶栈以及在常数时间内检索最小元素的堆栈。
这个栈需要支持常规栈的操作， 并且还能支持当前栈中的最小元素操作getMin方法。
getMin方法总是返回当前栈中的最小值。

力扣----最小栈

• 力扣提供的接口

class MinStack {

    public MinStack() {

    }
    
    public void push(int val) {

    }
    
    public void pop() {

    }
    
    public int top() {

    }
    
    public int getMin() {

    }
}

解决方法

1. 设计一个常规栈stackData正常压栈弹栈， 另外设计一个栈stackMin维护常规栈的最小值。

本题只需要想好压入逻辑就非常简单
假设压入数据为val。

• 若两个栈都为空， 则同步压入。
• 若不为空， 那么讨论val与stackMin栈顶元素的大小关系。因为stackMin维护的是最小值， 那么val<=,则stackMin压入val，否则，stackMin重复压入自身当前的堆顶元素。
• stackData全程进行常规压入操作。
• 由于两个栈都同时进行压入元素，不过对于stackMin要讨论压入的元素， 可以用一个size字段维护两个栈的大小

弹出逻辑
size--即可，两个栈的逻辑都视为弹出元素

public class MinStack {
	//题目所给的最大压入压出操作量， 假设全部压栈至多MAX
	public static int MAX = 30001;
	public int[] stackData = new int[MAX];
	public int[] stackMin = new int[MAX];
	public int size;//维护两个栈的长度， 因为是同步压入两个栈长度相同。
	public MinStack() {
		
	}

	public void push(int val) {
		if(size==0) {
			stackMin[size] = val;
		}
		else if(val <= stackMin[size-1]) {
			stackMin[size]=val;
		}
		else {
			stackMin[size] = stackMin[size-1];
		}
		stackData[size++] = val;
	}
	//常规栈操作
	public void pop() {
		size--;
	}
	//常规栈操作
	public int top() {
		return stackData[size-1];
	}
	//获取最小值
	public int getMin() {
		return stackMin[size-1];
	}	
}

100%优化环节

上面的栈是手动写的数组， 在算法篇---栈与队列基础说明了， 不过时间复杂度还是慢啊。
如果先前采用java内置栈的话， 效率肯定不如数组。
既然是做算法题， 反正也是单线程， 直接开静态数组。
也不要每次开30001大小的数组， 实测可以开更小的数组， 足以应付测试用例。
顺便优化以下push方法的逻辑。

public class MinStack {
	//题目所给的最大压入压出操作量， 假设全部压栈至多MAX
	public static int MAX = 7501;//实测7501足够了
	//减少每次测数据的开销， 直接空间复用
	public static int[] stackData = new int[MAX];
	public static int[] stackMin = new int[MAX];
	public static int size;//维护两个栈的长度， 因为是同步压入两个栈长度相同。
	public MinStack() {
		size = 0;//这里需要重置size。
	}

	public void push(int val) {
	//||优化
		if(size==0 || val <= stackMin[size-1]) {
			stackMin[size] = val;
		}
		else {
			stackMin[size] = stackMin[size-1];
		}
		stackData[size++] = val;
	}
	//常规栈操作
	public void pop() {
		size--;
	}
	//常规栈操作
	public int top() {
		return stackData[size-1];
	}
	//获取最小值
	public int getMin() {
		return stackMin[size-1];
	}	
}

结果: 击败100%的人。