LeetCode(剑指offer) Day1

1.用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解题过程记录：本题就是用两个栈，其中一个作为输入栈，另外一个作为输出栈，由于栈的特点是先进后出，有序数字全部进栈然后再出栈会使这个数字序列逆序，然后逆序数字序列再一次经过进栈出栈操作会再次逆序，经过这两次逆序，原本的数字序列的顺序会保持不变，符合队列先进先出的特点。

第一次提交未通过：出队列时，直接把输入栈的数字压入输出栈，忽略了此时输出栈中可能还会有数据，如果输出栈中有数据，序列顺序前后并不符合先进先出的特点。

class CQueue {Stack<Integer>s1=null,s2=null;public CQueue() {s1=new Stack<>();s2=new Stack<>();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {while(!s1.isEmpty()){s2.push(s1.pop());}if (s2.isEmpty()){return -1;}return s2.pop();}
}

第二次提交未通过：调用appendTail函数出队列，先判断s1输入栈中是否有数据，如果有并且s2输出栈中为空，将s1的数据全部压入s2输出栈，两栈全为空返回-1。思路混乱错误

class CQueue {Stack<Integer>s1=null,s2=null;public CQueue() {s1=new Stack<>();s2=new Stack<>();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {while(!s1.isEmpty()){if(s2.isEmpty()){s2.push(s1.pop());}}if (s2.isEmpty()){return -1;}return s2.pop();}
}

第三次提交通过： 只有出stack为空的时候，才将进stack的数据全部倒入出stack。

class CQueue {Stack<Integer>s1=null,s2=null;public CQueue() {s1=new Stack<>();s2=new Stack<>();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {if (s2.isEmpty()){if(s1.isEmpty()){return -1;}while(!s1.isEmpty()){s2.push(s1.pop());}}return s2.pop();}
}

2.定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。示例：

inStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

解法一：使用主栈s存储数字序列，用一个辅助栈stackTemp同步记录主栈中的最小值。具体来说，当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

class MinStack {/** initialize your data structure here. */Stack<Integer> s=null;Stack<Integer>stackTemp=null;public MinStack() {s=new Stack<>();stackTemp=new Stack<>();}public void push(int x) {s.push(x);if(stackTemp.isEmpty()){stackTemp.push(x);}else{stackTemp.push(Math.min(x,stackTemp.peek()));}}public void pop() {s.pop();stackTemp.pop();}public int top() {return s.peek();}public int min() {return stackTemp.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(x);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.min();*/

解法二：不使用辅助栈，保留当前最小值和差值，这种方法称为差值法。

解法思路讲解：差值法就是在向栈中插入数据的同时，同步记录并更新栈中的最小值，向栈中插入值x，栈中保存的不再是原值，而是x与最小值的差值即x-min。按照这种思路，push函数如下：

public void push(int x) {if (stack.isEmpty()) {stack.push(x);min = x;//栈为空，插入的第一个值作为当前最小值} else {stack.push(x - min);//栈不为空，后续插入栈中的值是x-minmin = Math.min(min, x);//每插入一个新值，需要同步更新最小值}}

入栈序列	5	2	3	-2	1
栈实际保存的值	5	-3	1	-4	3
当前最小值	5	2	2	-2	-2

如果用min记录当前栈中的最小值，用min与栈中的元素进行运算就很容易复原原序列的真实值。通过上面的表格举个例子，入栈序列：5 2 3 -2 1 经过x-min运算存入栈中实际值为 5 -3 1 -4 3。此时栈顶元素为3，是一个整数即x-min>0,也即x>min，说明x不是最小值，如果此时查看栈顶元素，直接返回min+栈顶元素即可复原真实值；但是如果栈顶元素为负数，说明入栈的元素比当前栈中的最小值还要小，那么最小值min就是原值x；还有一种特殊情况，由于我们向栈中插入第一个元素的时候，没有做x-min操作而是直接将真实值插入栈中，并且将它作为最小值，所以当栈中仅有一个元素的时候，栈顶元素=min=真实值。综合上述三种情况，故top函数：

 public int top() {if (stack.peek() < 0 || stack.size()==1) {return min;} else {return (min + stack.peek());}}

前面我们分析过，如果当前栈顶元素为正数，说明该元素不与最小值对应，可以直接pop，无需更新min;如果栈顶元素为负数，说明该元素与最小值对应，而且pop出的元素就是最小值，pop出后我们需要确定栈中剩余元素的最小值,假设push该元素的时候插入栈中的值为value,那么value=x-min，公式变形得min=x-value。经过上面的分析，pop函数为：

 public void pop() {if (stack.peek() < 0) {min = min - stack.pop();} else {stack.pop();}}

 我们回看push函数中的一行代码  stack.push(x - min)

 这里题目要求传入的值x是int类型，假设x为Integer.MAX_VALUE，min为Integer.MIN_VALUE，这样x-min运算势必会溢出，因此min需要改为long 类型，相关的算数运算也要在long类型下进行，因此代码优化为：

import java.util.Stack;public class MinStack {Stack<Long> stack = null;long min;public MinStack() {stack = new Stack<>();}public void push(int x) {if (stack.isEmpty()) {stack.push((long)x);min = (long)x;} else {stack.push((long)(x - min));min = Math.min(min, x);}}public void pop() {if (stack.peek() < 0) {min = min - stack.pop();} else {stack.pop();}}public int top() {if (stack.peek() < 0 || stack.size()==1) {return (int)min;} else {return (int)(min + stack.peek());}}public int min() {return (int)min;}
}