队列和栈

leetcode 20 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
   ```java //v1.0 利用栈的思想 class Solution { public boolean isValid(String s) {

    Map<Character,Character> map = new HashMap<>();
    map.put('(',')');
    map.put('[',']');
    map.put('{','}');
    LinkedList<Character> stack = new LinkedList<>(); 
    for(char c:s.toCharArray()){
        if(map.containsKey(c)) stack.add(c);
        else if(stack.size()==0||c!=map.get(stack.removeLast())) return false;
    }
    return stack.size()==0;

}

}

<a name="hWqkS"></a>
#### 
<a name="ru5X9"></a>
#### 剑指Offer 09 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )  
```java
class CQueue {
    private LinkedList<Integer> list1;
    private LinkedList<Integer> list2;
    public CQueue() {
        list1 = new LinkedList<>();
        list2 = new LinkedList<>();   
    }
    public void appendTail(int value) {
        list1.add(value);
    }
    public int deleteHead() {
        if(list2.size()!=0) return list2.removeLast();
        else if(list1.size() == 0) return -1;
        else{
            while(list1.size()!=0){
                list2.add(list1.removeLast());
            }
            return list2.removeLast();
        }
    }
}
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

leetcode 225用队列实现栈

class MyStack {
    private LinkedList<Integer> queue1;
    private LinkedList<Integer> queue2;
    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    /** Push element x onto stack. */
    public void push(int x) {
        if(queue1.size()!=0) queue1.add(x);
        else if(queue2.size()!=0) queue2.add(x);
        else queue1.add(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if(queue1.size()==0&&queue2.size()==0) return -1;
        else if(queue1.size()!=0){
            while(queue1.size()!=1){
                queue2.add(queue1.removeFirst());
            }
            return queue1.removeFirst();
        }        
        else{
            while(queue2.size()!=1){
                queue1.add(queue2.removeFirst());
            }
            return queue2.removeFirst();
        } 
    }
    /** Get the top element. */
    public int top() {
        int topNum;
        if(queue1.size()==0&&queue2.size()==0) return -1;
        else if(queue1.size()!=0){
            while(queue1.size()!=1){
                queue2.add(queue1.removeFirst());
            }
            topNum = queue1.getFirst();
            queue2.add(queue1.removeFirst());
            return topNum;
        }        
        else{
            while(queue2.size()!=1){
                queue1.add(queue2.removeFirst());
            }
            topNum = queue2.getFirst();
            queue1.add(queue2.removeFirst());
            return topNum;
        } 
    }
    /** Returns whether the stack is empty. */
    public boolean empty() {
        if(queue1.isEmpty()&&queue2.isEmpty()) return true;
        return false;
    }
}
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

leetcode84 柱状图中最大的矩形

可以把这个想象成锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板i矮了一截，那我就先找之前最戳出来的一块（其实就是第i-1块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高，那我继续单独计算这个次高木板的面积（应该是第i-1和i-2块），再把它俩锯短。直到发觉不需要锯就比第i块矮了，那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为0的木板。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] copy = new int[len+2];
        System.arraycopy(heights,0,copy,1,len);
        int area = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<len+2;i++){
            while(!stack.empty()&&(copy[stack.peek()]>copy[i])){
                int index = stack.pop();
                area = Math.max(area, copy[index]*(i-stack.peek()-1));
            }
            stack.push(i);
        }
        return area;
    }
}

leetcode85 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

class Solution {
    int area = 0;
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if(row==0){
            return 0;
        }
        int column = matrix[0].length;
        int[] heights = new int[row];
        // 以每一列的元素为基准，计算对应的高，(即1的连续个数)，总共执行column次的面积计算
        for(int colIndex=0; colIndex<column;colIndex++){
            for(int rowIndex=0; rowIndex<row;rowIndex++){
                int tmp = colIndex;
                while(tmp<column&&matrix[rowIndex][tmp]=='1'){
                    heights[rowIndex]++;
                    tmp++;
                }
            }
            countArea(heights);
            // 计算一次面积后，heights中元素置0
            for(int i =0;i<row;i++){
                heights[i]=0;
            }
        }
        return area;
    }
    public void countArea(int[] heights){
        int len = heights.length;
        int[] copy = new int[len+2];
        System.arraycopy(heights,0,copy,1,len);
        Stack<Integer> stack = new Stack<Integer>();
        for(int i=0;i<copy.length;i++){
            while(!stack.empty()&&copy[stack.peek()]>copy[i]){
                int index = stack.pop();
                area = Math.max(area, (i-stack.peek()-1)*copy[index]);
            }
            stack.push(i);
        }
    }
}