155 最小栈
题目信息
题目地址:https://leetcode-cn.com/problems/min-stack/
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.解法一：添加辅助栈
首先是具备栈的基本操作,除此之外添加了个获取最小元素的方法,也就是我们需要记录最小元素,但栈的元素变动有两种一种是入栈一种是出栈,这两种情况都会影响最小元素.所以我们没办法只用一个变量来记录最小值因为会回退,必须是容器存每个阶段最小值且变化逻辑与数据栈同步,这样一想的话就是再用一个栈呗.
如图:
这样的话，我们就是用另外一个栈记录最小值，并且可以跟随数据栈的变化回退或者添加，最终另外栈的顶部就是当前的最小值
下面我先手动实现个简单的栈再操作（因为是有两个栈都有基本操作，所以直接写在解题类里就会有重复，因此把栈的操作提出来），也可以就用java类库的栈
class MyStack {
private int[] data;
private int size = -1;
public MyStack() {
//data = new int[10000];
data = new int[50];
}
public void push(int x) {
// 是否需要扩容
size++;
if (size>data.length-1) {
data=Arrays.copyOf(data, data.length*2);
}
data[size] = x;
}
public void pop() {
size--;
}
public int peek() {
if(!isEmpty()){
// 抛异常
}
return data[size];
}
public boolean isEmpty(){
return size < 0;
}
}再用这个栈去是实现我们的最小栈：在入栈时判断当前元素是否比最小栈的栈顶要小，出栈时判断当前元素是否是最小栈的栈顶。
class MinStack {
MyStack data;
MyStack min;
public MinStack() {
data = new MyStack();
min = new MyStack();
}
public void push(int x) {
data.push(x);
if(min.isEmpty() || x <= min.peek()){
min.push(x);
}
}
public void pop() {
if(data.peek() == min.peek()){
min.pop();
}
data.pop();
}
public int top() {
return data.peek();
}
public int getMin() {
return min.peek();
}
}时间复杂度：只有栈的操作，无论是弹出还是压栈都是O(1)的操作 空间复杂度：定义了两个栈需要去存储数据，最差情况是2n，因此空间复杂度为O(n)
解法二：封装元素数据
与解法一一个逻辑，既然两个栈是同步的关系，把辅助栈的数据放到到通一个栈也可以。每个元素是一个对象其中不仅包含当前数值也包含当前最小栈里最小值
class StackNode{
private int value;
private int min;
public void setValue(int value){
this.value = value;
}
public void setMin(int min){
this.min = min;
}
public int getValue(){
return value;
}
public int getMin(){
return min;
}
}
代码如下：
class MinStack {
MyStack<StackNode> data;
public MinStack() {
data = new MyStack<StackNode>();
}
public void push(int x) {
StackNode node = new StackNode();
node.setValue(x);
if(data.isEmpty() || x <= data.peek().getMin()){
node.setMin(x);
}else{
node.setMin(data.peek().getMin());
}
data.push(node);
}
public void pop() {
data.pop();
}
public int top() {
return data.peek().getValue();
}
public int getMin() {
return data.peek().getMin();
}
}判定点与解法一一样，只是放到了同一元素的第二属性。上面我们写的栈MyStack是写死的数据类型int数组，这里要全部换成StackNode不如就写个泛型的上面的解也是用的这个栈，如下：
class MyStack<T> {
private T[] data;
private int size = -1;
public MyStack() {
//data = new int[10000];
data = (T[])new Object[50];
}
public void push(T x) {
// 是否需要扩容
size++;
if (size>data.length-1) {
data=Arrays.copyOf(data, data.length*2);
}
data[size] = x;
}
public void pop() {
size--;
}
public T peek() {
if(!isEmpty()){
// 抛异常
}
return data[size];
}
public boolean isEmpty(){
return size < 0;
}
}时间复杂度和空间复杂度与解一一样分别是O(1)与O(n)
总结
总体上是比较简单可以快的找到思路的，同时也多熟悉熟悉栈的数据结构。这次动图是用adobe的an画的以后大概都会用这个做。设计问题的两题就完结了下篇开始初级的合集的数学问题