剑指offer：Day1
题目1
解题思路
使用两个栈去实现队列，所以我们要对栈和队列的特性要有所了解
栈的特性就是先进后出，而队列的特性是先进先出，假如现在有两个杯子，一个杯子装满了水，怎么利用另外一个杯子去获取装满水的杯子的最下层的水，答案就是：将水转移进另外一个杯子，那么此时杯子的水最上层的就是原先最下层的水
就像下面这样
给出V1版代码
class CQueue {
//使用两个杯子
//one杯子用来装水
//two杯子用来置换水
private Stack<Integer> one;
private Stack<Integer> two;
public CQueue() {
one = new Stack<Integer>();
two = new Stack<Integer>();
}
public void appendTail(int value) {
//加水的时候直接往one杯子加即可
one.push(value);
}
/**
* 这种方法每次都要取倒腾，很慢
* @return
*/
public int deleteHead() {
//如果one杯子没水，不需要转移，并且返回-1代表没水
if(one.isEmpty()){
return -1;
}
//如果one杯子有水，将水转移进two杯子中
//只留下最下层的水在one杯子中
while (one.size() > 1){
two.push(one.pop());
}
//取出one杯子剩下的最下层的水，等待返回
//此时one杯子已经没水了
Integer result = one.pop();
//将two杯子中的水再放回去one杯子中
//准备下一次同样取最下层的水
while (!two.isEmpty()){
one.push(two.pop());
}
//返回最下层的水
return result;
}
}
但这种做法的不足之处在于每一次转移水后，都要把取剩下的水放回原处，那能不能进行优化呢？
是可以进行优化的，当我们将one杯子中的水转移进two杯子后，就不再倒回去one杯子，下次取的时候，从two杯子里面取，直到two杯子为空再从one杯子里面去拿
下面来看看V2版本
class CQueueTwo{
private Stack<Integer> one;
private Stack<Integer> two;
public CQueueTwo() {
one = new Stack<Integer>();
two = new Stack<Integer>();
}
//加水的时候，还是直接往one杯子中加水
public void appendTail(int value) {
one.push(value);
}
/**
* 为什么不等水空了再考虑去接呢？
* @return
*/
public int deleteHead() {
//two杯子中的水是空的，所以从one杯子中重新接
if(two.isEmpty()){
while (!one.isEmpty()){
two.push(one.pop());
}
//取完水后，判断取的水是不是空的
if(!two.isEmpty()){
//不是空就返回上层水即可
return two.pop();
}
return -1;
}
//如果two杯子中水没空，继续从中取
return two.pop();
}
}
我们还可以继续优化一下取水过程，下面给出V3版本
/**
* 为什么不等水空了再考虑去接呢？
* 再继续优化一下
* @return
*/
public int deleteHead() {
//要取出的水空了，需要去重新接
if(two.isEmpty()){
while (!one.isEmpty()){
two.push(one.pop());
}
if(two.isEmpty()){
return -1;
}
}
//如果水没空，继续从中取
return two.pop();
}
题目2
解题思路
push和pop使用O(1)方法都很容易，但重点在于如何O(1)实现min方法
为了O(1)实现min方法，所以我们需要用到一个辅助栈，这个辅助栈从栈顶到栈底依次从小到大记录着添加进栈的数据，如果全部入栈的都要进行记录，那是很难维护辅助栈的，所以我们要知道记录哪些元素即可。
-
栈的优点是先进后出，那么对于比第一个进的元素大的后面元素是不需要进来辅助栈的，因为后面进的比较大的元素弹出了，底下比较小的元素都没有被弹出，最小值依然为底下最小的元素，所以不需要记录，所以我们可以设置一个变量来记录push进来的元素最小值，只有比该变量小的元素才能进辅助栈，成为新的最小值
-
当最小元素被弹出后，要重新定义可以允许进来的最小值，否则会影响后面元素进入辅助栈，因为最小元素被弹出，所以辅助栈对应的元素也被弹出，那么可以允许进来的最小值应该变为辅助栈的第二小的元素
代码如下
static class MinStack {
//one来记录新增的元素
//two为辅助栈
private Stack<Integer> one;
private Stack<Integer> two;
private int recordMin;
/** initialize your data structure here. */
public MinStack() {
this.one = new Stack<Integer>();
this.two = new Stack<Integer>();
}
//新增元素方法
public void push(int x) {
//假如是第一次插入
if(this.one.isEmpty()){
//记录第一次插入元素的值为允许进去辅助栈的最大值
//只有比这值还小的元素才能继续进入辅助栈
this.recordMin = x;
//并且插入进辅助栈中
this.two.push(recordMin);
}
//以后的插入，如果小于这个值才允许进入辅助栈
//并且更新可以进去辅助的最大值
else if(x <= this.recordMin){
//更新recordMin
this.recordMin = x;
two.push(x);
}
//最后都要进入栈中
this.one.push(x);
}
//弹出方法
public void pop() {
//先取出要弹出的数据
Integer pop = this.one.pop();
if(!two.isEmpty()){
//比较辅助栈的最小值是不是与其相等
//因为比其小的在下面未弹出，所以只可能比其大或者相等
//比其大就不需要管
if(pop.equals(this.two.peek())){
//如果与其相等
//辅助栈也要弹出，并且要更新允许进入辅助栈的最大值
this.two.pop();
if(this.two.isEmpty()){
//更新进入辅助栈的最大值为辅助栈第二小的值，也就是此时的栈顶
//（因为上面已经弹出）
this.recordMin = this.two.peek();
}
}
}
}
public int top() {
return this.one.peek();
}
public int min() {
return this.two.peek();
}
}