剑指 Offer 31.栈的压入、弹出序列">1、剑指 Offer 31.栈的压入、弹出序列
剑指 Offer 09.用两个栈实现队列">2、剑指 Offer 09.用两个栈实现队列
剑指 Offer 59 - II.队列的最大值">4、剑指 Offer 59 - II.队列的最大值
42. 接雨水">6、42. 接雨水

1、剑指 Offer 31.栈的压入、弹出序列

这道题思路是正确的，竟然写不出代码……
小米一面算法题，日了…..

1.1 题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true 解释：我们可以按以下顺序执行： push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false 解释：1 不能在 2 之前弹出。

1.2 思路

初始化一个双向队列stack，一个指向popped数组的指针index；
将pushed数组中的元素依次压入stack中；
先压入pushed中的元素，再进行判断，注意这里用while循环判断，如果stack的末尾元素与popped数组中的首元素相等，则将stack的末尾元素移除，index向后移动一位，循环往复，直到stack的末尾元素与index指向的元素不相等，再跳出循环，pushed数组中的元素再继续压入stack；

当stack为空，则返回true。

1.3 代码

class Solution {
 public boolean validateStackSequences(int[] pushed, int[] popped) {
     LinkedList<Integer> stack = new LinkedList<>();
     int index = 0;
     for (int push: pushed) {
         stack.addLast(push);
         while (!stack.isEmpty() && stack.peekLast() == popped[index]) {
             stack.pollLast();
             ++index;
         }
     }
     return stack.isEmpty();
 }
}

2、剑指 Offer 09.用两个栈实现队列

2.1 题目

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

输入： [“CQueue”,”appendTail”,”deleteHead”,”deleteHead”] [[],[3],[],[]] 输出：[null,null,3,-1]

示例 2：

输入： [“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”] [[],[],[5],[2],[],[]] 输出：[null,-1,null,null,5,2]

2.2 思路

stack1只负责插入元素；
每次删除的时候，把stack1里的元素出栈并入栈到stack2中，此时stack2中的顺序就是元素入队的顺序，再将stack2首元素弹出，然后stack2里的元素出栈并入栈回stack1，最后返回弹出的元素。
2.3 代码
```java import java.util.Stack;

class CQueue {

private Stack<Integer> stack1;
private Stack<Integer> stack2;
public CQueue() {
    stack1 = new Stack<>();
    stack2 = new Stack<>();
}
public void appendTail(int value) {
    stack1.add(value);
}
public int deleteHead() {
    if (stack1.isEmpty()) {
        return -1;
    }
    while (!stack1.isEmpty()) {
        stack2.add(stack1.pop());
    }
    int res = stack2.pop();
    while (!stack2.isEmpty()) {
        stack1.add(stack2.pop());
    }
    return res;
}

}

<a name="yxJ8h"></a>
# 3、[剑指 Offer 30.包含min函数的栈](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/)
<a name="P5cyu"></a>
## 3.1 题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数，在该栈中调用 min、push 及 pop 的时间复杂度都是 O(1)。<br />示例:
> MinStack minStack = new MinStack();
> minStack.push(-2);
> minStack.push(0);
> minStack.push(-3);
> minStack.min();   --> 返回 -3.
> minStack.pop();
> minStack.top();      --> 返回 0.
> minStack.min();   --> 返回 -2.
<a name="dzTHW"></a>
## 3.2 思路
1. 两个栈，dataStack存栈中正常入栈的元素，minStack存放栈中不同元素状态下的最小值；
1. 入栈时，minStack存放当前minStack的栈顶元素与x的最小值；
1. 出栈时，两个栈都要pop；
1. 求最小值时，仅需minStack.peek()即可。
<a name="bV7zX"></a>
## 3.3 代码
```java
import java.util.Stack;
class MinStack {
    // 存数据的栈
    private Stack<Integer> dataStack;
    // 存最小值的栈
    private Stack<Integer> minStack;
    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }
    public void push(int x) {
        dataStack.push(x);
        if (minStack.isEmpty()) {
            minStack.push(x);
        } else {
            minStack.push(minStack.peek() < x? minStack.peek(): x);
        }
    }
    public void pop() {
        dataStack.pop();
        minStack.pop();
    }
    public int top() {
        return dataStack.peek();
    }
    public int min() {
        return minStack.isEmpty()? -1: minStack.peek();
    }
}

4、剑指 Offer 59 - II.队列的最大值

4.1 题目

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1。
示例 1：

输入: [“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”] [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]

示例 2：

输入: [“MaxQueue”,”pop_front”,”max_value”] [[],[],[]] 输出: [null,-1,-1]

4.2 思路

难点在于获取队列的最大值时，需要维护一个单调递减的最大值队列，这个最大值队列的首元素就是当前队列中元素的最大值。原理是：当一个元素入队时，基于队列的后进后出的原则，它前面所有比它小的元素都不会对最大值产生影响了；
插入时，将最大值队列中所有比当前要插入的元素value小的元素都出队，直到遇到最大值队列中比value大的元素为止，然后再将value插入最大值队列的尾部；
出队时，判断当前出队的元素值是否等于最大值队列的首元素，等于时将最大值队列的首元素也出队。
4.3 代码
```java import java.util.Deque; import java.util.LinkedList; import java.util.Queue;

class MaxQueue {

private Queue<Integer> dataQueue;
private Deque<Integer> maxQueue;
public MaxQueue() {
    dataQueue = new LinkedList<>();
    maxQueue = new LinkedList<>();
}
public int max_value() {
    return maxQueue.isEmpty()? -1: maxQueue.peekFirst();
}
public void push_back(int value) {
    dataQueue.add(value);
    while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
        maxQueue.removeLast();
    }
    maxQueue.addLast(value);
}
public int pop_front() {
    if (dataQueue.isEmpty()) {
        return -1;
    }
    int res = dataQueue.poll();
    if (!maxQueue.isEmpty() && maxQueue.peekFirst() == res) {
        maxQueue.removeFirst();
    }
    return res;
}

}

<a name="Ww0gV"></a>
# 5、[739. 每日温度](https://leetcode-cn.com/problems/daily-temperatures/)
维护一个单调递减的栈，这道题太难想了.....
<a name="zIbMd"></a>
## 5.1 题目
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。<br />**示例 1:**
> **输入**: temperatures = [73,74,75,71,69,72,76,73] **输出**: [1,1,4,2,1,1,0,0]
<a name="jn174"></a>
## 5.2 思路
1. 维护一个单调递减的栈，这个栈存放的是元素的下标，单调递减是指栈中的存放的下标对应的温度在栈中是单调递减的。不一定非是单调递减的栈，但调递减的队列也行，反正实现类都是LinkedList；
1. 遍历temperatures数组，对数组中的每一个元素：
   1. 当栈顶元素对应的温度  >= 当前元素对应的温度，直接将当前元素入栈；
   1. 当栈顶元素对应的温度 < 当前元素对应的温度，将栈顶元素弹出直到栈顶元素重新 > 当前元素，对弹出的元素，元素值即为res数组的下标，下标在res数组中对应的值是当前遍历数组元素的下标 - 弹出的栈顶元素的值。
<a name="SZe90"></a>
## 5.3 代码
```java
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        // stack存放元素在temperatures数组中的下标
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < temperatures.length; ++i) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peekFirst()]) {
                int preIndex = stack.pollFirst();
                res[preIndex] = i - preIndex;
            }
            stack.addFirst(i);
        }
        return res;
    }
}

6、42. 接雨水

经典高频，但是我不会……
背下来！

6.1 题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

6.2 思路

题解：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
单调栈

6.3 代码

class Solution {
    public int trap(int[] height) {
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < height.length; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[i], height[left]) - height[top];
                res += currWidth * currHeight;
            }
            stack.push(i);
        }
        return res;
    }
}

数据结构和算法

栈队列

1、剑指 Offer 31.栈的压入、弹出序列

1.1 题目

1.2 思路

1.3 代码

2、剑指 Offer 09.用两个栈实现队列

2.1 题目

2.2 思路

2.3 代码

4、剑指 Offer 59 - II.队列的最大值

4.1 题目

4.2 思路

4.3 代码

6、42. 接雨水

6.1 题目

6.2 思路

6.3 代码