private List<Integer> result;
//一圈一圈进行打印，当左上角元素在右下角元素的上方或者右方时结束
public List<Integer> spiralOrder(int[][] matrix) {
    result = new ArrayList<>();
    if(matrix.length==0||matrix[0].length==0){
        return result;
    }
    int left_row = 0;
    int left_col = 0;
    int right_row = matrix.length-1;
    int right_col = matrix[0].length-1;
    while(left_row<=right_row&&left_col<=right_col){
        helper(matrix,left_row++,left_col++,right_row--,right_col--);
    }
    return result;
}

/**打印一圈元素局灶性，这实际上是一个矩形，需要传递该矩形的左上角以及左下角坐标
     * 当两个坐标同行，直接打印
     * 当两个坐标同列，直接打印
     * 两个坐标不同行也不同列：
     *
     */
public void helper(int[][] matrix,int left_row,int left_col,int right_row,int right_col){
    if(left_row==right_row){
        for(int i= left_col;i<=right_col;i++){
            result.add(matrix[left_row][i]);
        }
    }else if(left_col==right_col){
        for(int i= left_row;i<=right_row;i++){
            result.add(matrix[i][left_col]);
        }
    }else{
        int curCol = left_col;
        while(curCol!=right_col){
            result.add(matrix[left_row][curCol]);
            curCol++;
        }
        int curRow = left_row;
        while(curRow!=right_row){
            result.add(matrix[curRow][right_col]);
            curRow++;
        }

        while(curCol!=left_col){
            result.add(matrix[right_row][curCol]);
            curCol--;
        }
        while(curRow!=left_row){
            result.add(matrix[curRow][left_col]);
            curRow--;
        }
    }
}

/**
     * 当a点走完最后一个点，可以结束循环
     * 执行完一次对角线打印，坐标变换方式：
     * b：先下，走到底了，再右
     * a：先右，走到最右，再下
     * */
 private int arr_index= 0;
public int[] findDiagonalOrder(int[][] matrix) {

    if(matrix.length==0||matrix[0].length==0){
        return new int[0];
    }
    int[] result = new int[matrix.length*matrix[0].length];
    arr_index = 0;
    boolean form = false;
    int row_lenth = matrix.length-1;
    int col_length = matrix[0].length-1;
    int a_row =0,b_row = 0,a_col=0,b_col=0;
    //a到达最后一个节点
    while(a_row<=row_lenth){
        helper(matrix,a_row,a_col,b_row,b_col,form,result);
        if(a_col<col_length){
            a_col++;
        }else{
            a_row++;
        }
        if(b_row<row_lenth){
            b_row++;
        }else{
            b_col++;
        }
        form=!form;
    }
    return result;

}
/**
     * 打印一个对角，a为右上角元素，b为左下角元素
     * 因为有左到右以及右到左两种方式交替，所以需要一个form参数
     * 右到左：a_row>=b_row 赋值 移动到做下第一个点:a_row--  a_col--
     * */
public void helper(int[][] matrix,int a_row,int a_col,int b_row,int b_col,boolean form,int[] result){
    if(form){
        while(a_row<=b_row&&a_col>=b_col){
            result[arr_index++] = matrix[a_row++][a_col--];
        }
    }else{
        while(a_row<=b_row&&a_col>=b_col){
            result[arr_index++] = matrix[b_row--][b_col++];
        }
    }
}

//使用index来代表栈顶位置，index=0，栈为空，index = size，栈满
public class ArrStack {
    private int[] arr;
    private int index;
    public ArrStack(int size){
        arr = new int[size];
    }
    public void push(int x){
        if(index==arr.length){
            throw new ArrayIndexOutOfBoundsException("full");
        }
        arr[index++] = x;
    }

    public int  pop(){
        if(index==0){
            throw new ArrayIndexOutOfBoundsException("empty");
        }
        return arr[--index];
    }
    public int  peek(){
        if(index==0){
            throw new ArrayIndexOutOfBoundsException("empty");
        }
        return arr[index-1];
    }
    public boolean isEmpty(){
        return index==0;
    }
}

public class MyCircularQueue {
    /**
     * 记录队头的front，记录队尾的wear，size表示队列大小
     * front指向第一个元素 rear指向最后一个元素后一个位置
     * 入队：arr[rear]=value，rear后移，size++，注意，因为要完成一个循环队列rear+1需要取模运算
     * 出队：font后移取模运算，size--
     * */
    private int front = 0;
    private int rear = 0;
    private int size = 0;
    private int[] arr;
    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        arr = new int[size];
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if(size==arr.length){
            return false;
        }
        arr[rear] = value;
        rear = (rear +1)%arr.length;
        size++;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if(size==0){
            return false;
        }
        front = (front++)%arr.length;
        size--;
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if(size==0){
            throw new RuntimeException("empty");
        }
        return arr[front];
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if(size==0){
            throw new RuntimeException("empty");
        }
        return arr[(rear-1)%arr.length];
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return size==0;
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return size==arr.length;
    }
}

Stack<Integer> data = new Stack<>();
Stack<Integer> min = new Stack<>();
public MinStack() {

}

/**入栈的时候除了data栈之外，还包括min栈，存储的每一个元素其相应的最小值
     *
     */

public void push(int x) {
    data.push(x);
    if(min.isEmpty()){
        min.push(x);
    }else{
        int minVal = min.peek();
        if(x<minVal){
            min.push(x);
        }else{
            min.push(minVal);
        }
    }

}

public void pop() {
    if(!data.isEmpty()) {
        data.pop();
        min.pop();
    }else{
        throw new ArrayIndexOutOfBoundsException("empty");
    }
}

public int top() {
    int res = 0;
    if(!data.isEmpty()) {
        res = data.peek();
    }else{
        throw new ArrayIndexOutOfBoundsException("empty");
    }
    return res;
}

public int getMin() {
    int res = 0;
    if(!min.isEmpty()) {
        res = min.peek();
    }else{
        throw new ArrayIndexOutOfBoundsException("empty");
    }
    return res;
}

private Queue<Integer> data = new LinkedList<>();
private Queue<Integer> helper = new LinkedList<>();
private int top;
public MyStack() {

}

/** 放入到data队列中 */
public void push(int x) {
    data.add(x);
}

/** pop元素的时候，将前n-1个元素放入helper中，只留下最后一个元素，这样，就可以达到栈的目的
     * */
public int pop() {
    while(data.size()>1){
        helper.add(data.remove());
    }
    int res = data.remove();
    swap();
    return res;
}
public void swap(){
    Queue<Integer> tmp = this.data;
    this.data = this.helper;
    this.helper = tmp;
}
/** Get the top element. */
public int top() {
    while(data.size()>1){
        helper.add(data.poll());
    }
    int res = data.poll();
    helper.add(res);
    swap();
    return res;
}

/** Returns whether the stack is empty. */
public boolean empty() {
    return data.size()==0;
}

Stack<Integer> sta_pop = new Stack<>();
/** Initialize your data structure here. */
public MyQueue() {

}

/** Push element x to the back of queue. */
public void push(int x) {
    pushtoPop();
    sta_push.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
    pushtoPop();
    return sta_pop.pop();
}

/** Get the front element. */
public int peek() {
    pushtoPop();
    return sta_pop.peek();
}
//将元素从push推到pop
//1.一次性推完push中元素 2.pop中为空
public void pushtoPop(){
    if(sta_pop.isEmpty()) {
        while (!sta_push.isEmpty()) {
            sta_pop.push(sta_push.pop());
        }
    }
}

/** Returns whether the queue is empty. */
public boolean empty() {
    return sta_pop.isEmpty()&&sta_push.isEmpty();
}

public int minDepth(TreeNode root) {
    return helper(root);
}

/**
     * 左右节点均不为空使，返回min(left,right)+1
     * 左右节点只有一个为空（left==null）时，需要返回right+1，而不是返回min(lef,right)+1
     * */
public int helper(TreeNode root){
    if(root==null){
        return 0;
    }
    int left = helper(root.left);
    int right = helper(root.right);
    if(root.left==null||root.right==null){
        return left+right+1;
    }
    return Math.min(left,right)+1;
}

/*
左子树的所有点应该在(minVal,root),右子树在(root,maxVal)
*/
public boolean isValidBST(TreeNode root) {
    return helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
}

public boolean helper(TreeNode root,long minVal,long maxVal){
    if(root==null){
        return true;
    }
    if(root.val<=minVal||root.val>=maxVal){
        return false;
    }
    return helper(root.left,minVal,root.val)&&helper(root.right,root.val,maxVal);
}

public boolean isValidBST(TreeNode root) {
    boolean isRoot = true;
    if(root==null){
        return true;
    }
    Stack<TreeNode> stack = new Stack<>();
    int last = Integer.MIN_VALUE;
    while(!stack.isEmpty()||root!=null){
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
        if(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(isRoot){
                last = node.val;
                isRoot = false;
            }else if(node.val>last){
                last = node.val;
            }else{
                return false;
            }
            //dayin
            root = node.right;
        }
    }
    return true;
}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while(!stack.isEmpty()||root!=null){
        while(root!=null){
            stack.push(root);
            result.add(root.val);
            root = root.left;
        }
        if(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            root = node.right;
        }
    }
    return result;
}

/**
     * 将root的最左的元素全部压入栈，当root==null，表示压到底了，最左侧已经没有元素了，此时，可以将栈顶元素取出
     * 并开始对右子树做同样操作
     * */
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while(!stack.isEmpty()||root!=null){
        while (root!=null){
            stack.push(root);
            root = root.left;
        }
        if(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            root = node.right;
        }
    }
    return result;
}

/**
     * 前序根右左，反转为左右根即可
     * */
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while(!stack.isEmpty()||root!=null){
        while(root!=null){
            result.add(0,root.val);
            stack.push(root);
            root = root.right;
        }
        if(!stack.isEmpty()){
            TreeNode node = stack.pop();
            root = node.left;
        }
    }
    return result;
}

/**
     * 两个根节点值相等
     * 左边的左子树和右边的右子树相等
     * 左边的右子树和右边的左子树相等
     * */
public boolean isSymmetric(TreeNode root) {
    //一般二叉树的题目首先判断是否null
    if(root==null){
        return true;
    }
    return helper(root,root);
}

public boolean helper(TreeNode p,TreeNode q){
    // 两个节点同时为空，返回true 只有一个节点为空，返回false
    if(p==null||q==null){
        return p==null&&q==null;
    }
    return p.val==q.val&&helper(p.left,q.right)&&helper(p.right,q.left);
}

/**
     *对称树的话，对于根节点的左右子树分别进行左根右以及右左根应该是相同的
     * */
public boolean isSymmetric(TreeNode root) {
    if(root==null){
        return true;
    }
    return inOrder(root.left,root.right);
}

public boolean inOrder(TreeNode left ,TreeNode right){
    Stack<TreeNode> s_left = new Stack<>();
    Stack<TreeNode> s_right = new Stack<>();
    while (left!=null||right!=null||!s_left.isEmpty()||!s_right.isEmpty()){
        while(left!=null&&right!=null){
            s_left.push(left);
            s_right.push(right);
            left = left.left;
            right = right.right;
        }
        //假如left与right不等，表明左子树个数不一样，必定不同
        if(left!=right){
            return false;
        }

        if(s_left!=null&&s_right!=null){
            TreeNode leftnode = s_left.pop();
            TreeNode rightnode = s_right.pop();
            if(leftnode.val!=rightnode.val){
                return false;
            }
            left = leftnode.right;
            right = rightnode.left;
        }
    }
    return true;
}

public TreeNode buildTree(int[] preorder, int[] midorder) {
    //设置一个map存储索引位置，查询方便
    HashMap<Integer,Integer> midorder_index = new HashMap<>();
    for(int i=0;i<midorder.length;i++){
        midorder_index.put(midorder[i],i);
    }
    return helper(preorder,midorder,0,preorder.length-1,0,preorder.length-1,midorder_index);
}
/**
     * preorder[p_start]是根节点，这样就可以找到preorder[p_start]在中序遍历中的位置，这样，就可以获得左子树以及右子树的范围，接着递归来做
     * */
public TreeNode helper(int[] preorder , int[] midorder, int p_start, int p_end, int m_start, int m_end, Map<Integer,Integer> midorder_index){
    //此时没有元素了，直接返回null
    if(p_start>p_end){
        return null;
    }
    //获取根节点
    int root_val = preorder[p_start];
    TreeNode root = new TreeNode(root_val);
    int index = midorder_index.get(root_val);
    //左子树的长度
    int length = index - m_start;
    root.left = helper(preorder,midorder,p_start+1,p_start+length,m_start,index-1,midorder_index);
    root.right = helper(preorder,midorder,p_start+length+1,p_end,index+1,m_end,midorder_index);
    return root;

}

public TreeNode buildTree(int[] inorder, int[] postorder) {
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<inorder.length;i++){
        map.put(inorder[i],i);
    }
    return helper3(inorder,postorder,0,inorder.length-1,0,inorder.length-1,map);
}
public TreeNode helper3(int[] inorder, int[] postorder,int i_start,int i_end,int p_start,int p_end,Map<Integer,Integer> map){
    if(i_start>i_end){
        return null;
    }
    if(i_start==i_end){
        return new TreeNode(postorder[p_start]);
    }
    int root_val = postorder[p_end];
    int index = map.get(root_val);
    int length = index - i_start;
    TreeNode root = new TreeNode(root_val);
    root.left = helper3(inorder,postorder,i_start,index-1,p_start,p_start+length-1,map);
    root.right = helper3(inorder,postorder,index+1,i_end,p_start+length,p_end-1,map);
    return root;
}

public TreeNode constructFromPrePost(int[] pre, int[] post) {
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<pre.length;i++){
        map.put(post[i],i);
    }
    return helper2(pre,post,0,pre.length-1,0,pre.length-1,map);
}

public TreeNode helper2(int[] pre, int[] post, int pre_start, int pre_end, int post_start, int post_end, Map<Integer,Integer> map){
    if(pre_start>pre_end){
        return null;
    }
    if(pre_start==pre_end){
        return new TreeNode(pre[pre_start]);
    }

    int root_val = pre[pre_start];
    int left_val = pre[pre_start+1];
    int index = map.get(left_val);
    TreeNode root = new TreeNode(root_val);
    int length = index-post_start;
    root.left = helper2(pre,post,pre_start+1,pre_start+1+length,post_start,index,map);
    root.right  = helper2(pre,post,pre_start+1+length+1,pre_end,index+1,post_end-1,map);
    return root;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if(root==null){
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while(queue.size()>0){
        List<Integer> vals = new ArrayList<>();
        int size = queue.size();
        for(int i=0;i<size;i++){
            TreeNode node = queue.remove();
            vals.add(node.val);
            if(node.left!=null) {
                queue.add(node.left);
            }
            if(node.right!=null) {
                queue.add(node.right);
            }
        }
        result.add(vals);
    }
    return result;
}

/**
     * 后序遍历二叉树。
     * 左子树返回不为空，右子树返回不为空，则该node必定是公共祖先
     * */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //当前节点==p或者==q，那么该点必定是祖先
    if(root==null||root==p||root==q){
        return root;
    }
    //递归左右子树
    TreeNode left = lowestCommonAncestor(root.left,p,q);
    TreeNode right = lowestCommonAncestor(root.right,p,q);
    //假如左右子树返回均不为空，那么当前节点就是公共祖先
    if(left!=null&&right!=null){
        return root;
    }
    //只有一个子树返回的不是空
    return left!=null?left:right;
}

/**
     * 某一个节点的直径=左子树深度+右子树深度
     * 树的深度 = max(左子树深度,右子树深度)+1
     * 因为要求任意两个节点的直径，所以还需要一个ans记录当前直径的最大值
     * */
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
    helper(root);
    return ans;
}
//helper返回的是树的深度，而直径最大值采用ans来记录
public int helper(TreeNode root){
    if(root==null){
        return 0;
    }
    //左右子树的深度
    int left = helper(root.left);
    int right = helper(root.right);
    //计算该点的直径，并与最大直径比较
    int zhijing = left+right;
    ans = zhijing>ans?zhijing:ans;
    //返回树的深度
    return (left>right?left:right)+1;
}

int res=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    return helper(root);
}
public int helper(TreeNode root){
    if(root==null){
        return 0;
    }
    int left = helper(root.left);
    int right = helper(root.right);
    int root_res = left+right+root.val;
    res = Math.max(root_res,res);
    return Math.max(0,Math.max(left,right)+root.val);
}

class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        int res = node.val;
        node = node.right;
        while(node!=null){
            stack.push(node);
            node = node.left;
        }
        return res;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

/**
     * 中序遍历：左根右
     * 所以，假如该节点有右子树，那么后继节点是右子树的最左一个节点
     * 假如该节点没有右子树，那么他一定是某一个节点p的左子树的最右节点，因此该节点后继节点就是p
     * */
public TreeNode getSuccessorNode(TreeNode node){
    if(node==null){
        return null;
    }
    if(node.right!=null){
        return getRightMostLeft(node.right);
    }else{
        TreeNode parent = node.parent;
        while(parent!=null&&parent.left!=node){
            node = node.parent;
            parent = node.parent;
        }
        return parent;
    }
}

public TreeNode getRightMostLeft(TreeNode node){
    while(node.left!=null){
        node = node.left;
    }
    return node;
}

public String serialize(TreeNode root) {
    if(root==null){
        return "#!";
    }
    String res = root.val+"!";
    res += serialize(root.left);
    res+= serialize(root.right);
    return res;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] values = data.split("!");
    Queue<String> queue = new LinkedList<>();
    for(String s:values){
        queue.add(s);
    }
    return recoverFromPre(queue);
}

public TreeNode recoverFromPre(Queue<String> queue){
    String value = queue.poll();
    if(value.equals("#")){
        return null;
    }else{
        TreeNode root = new TreeNode(Integer.parseInt(value));
        root.left = recoverFromPre(queue);
        root.right = recoverFromPre(queue);
        return root;
    }
}

public String serialize(TreeNode root) {
    if(root==null){
        return "#!";
    }
    StringBuilder res=  new StringBuilder(root.val+"!");
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(queue.size()>0){
        TreeNode node = queue.poll();
        if(node.left!=null){
            queue.add(node.left);
            res.append(node.left.val+"!");
        }else{
            res.append("#!");
        }
        if(node.right!=null){
            queue.add(node.right);
            res.append(node.right.val+"!");
        }else{
            res.append("#!");
        }
    }
    return res.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] values = data.split("!");
    int index = 0;
    if(values[0].equals("#")){
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode root = new TreeNode(Integer.parseInt(values[index++]));
    queue.add(root);
    while(queue.size()>0){
        TreeNode node =  queue.poll();
        String s_left = values[index++];
        String s_right = values[index++];
        if(s_left.equals("#")){
            node.left = null;
        }else{
            node.left = new TreeNode(Integer.parseInt(s_left));
            queue.add(node.left);
        }
        if(s_right.equals("#")){
            node.right = null;
        }else{
            node.right = new TreeNode(Integer.parseInt(s_right));
            queue.add(node.right);
        }
    }
    return root;
}

public boolean isBalanced(TreeNode root) {
    isBalance = true;
    healperBalance(root);
    return isBalance;
}

private boolean isBalance = true;
//返回树的高度
public int  healperBalance(TreeNode root){
    if(root==null){
        return 0;
    }
    int left = healperBalance(root.left);
    int right = healperBalance(root.right);
    if(Math.abs(left-right)>1){
        isBalance = false;
    }
    return Math.max(left,right)+1;
}

/**
     * 层序遍历，设置一个停止标志，遇到空节点，停止标志为真，如果停止标志为真，再遍历遇到非空节点，则非完全二叉树。
     * */
public boolean isCompleteTree(TreeNode root) {
    if(root==null){
        return true;
    }
    //当遇到第一个空节点时，将firstFull设置为true，假如是完全二叉树，后面所有节点都应该是空节点，不会再遇到非空节点
    boolean firstNull = false;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(queue.size()>0) {
        TreeNode node = queue.poll();
        if (node.left != null) {
            queue.add(node.left);
            //假如firstNull==true，该非空节点前面有一个空节点，必定不是完全二叉树
            if (firstNull) {
                return false;
            }
        } else {
            //第一个非空节点，记录标志
            if (!firstNull) {
                firstNull = true;
            }
        }
        if (node.right != null) {
            queue.add(node.right);
            if (firstNull) {
                return false;
            }
        } else {
            if (!firstNull) {
                firstNull = true;
            }
        }

    }
    return true;
}

/**
     * 寻找root右子树的最左节点，假如该节点位于最后一层，那么root的左子树必定是满二叉树，可以计算出节点个数，对于右子树，继续递归
     * 假如该节点位于倒数第二层，那么右子树是满二叉树，同理可计算
     * */
private int height = 0;
public int countNodes(TreeNode root) {
    if(root==null){
        return 0;
    }
    height = getHeight(root,1);
    return helpCount(root,1);
}
public int getHeight(TreeNode root,int level){
    while(root!=null){
        level++;
        root = root.left;
    }
    return level-1;
}
public int helpCount(TreeNode root,int level){
    if(level==height){
        return 1;
    }
    //获取右子树最左节点的层数
    int leftMostheight = getHeight(root.right,level+1);
    //最左节点位于最后一层，左子树是满二叉树
    if(leftMostheight==height){
        return (1<<(height-level))+helpCount(root.right,level+1);
    }else{
        return (1<<(height-level-1))+helpCount(root.left,level+1);
    }
}

/**
     * 因为nums1是nums2的子集，所以只需要求出nums2中的每一个元素的下一个更大元素即可，存储在map中，使用单调递增来解决
     * 遍历nums2，当栈顶元素比他小的时候，该元素是没有用的，将其踢出栈，并入栈
     * 当栈顶元素大于该元素的时候，保留栈顶元素，入栈
     * */
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    HashMap<Integer,Integer> map = new HashMap<>();
    Stack<Integer> stack = new Stack<>();
    for(int i=nums2.length-1;i>=0;i--){
        while(!stack.isEmpty()&&stack.peek()<=nums2[i]){
            stack.pop();
        }
        map.put(nums2[i],stack.isEmpty()?-1:stack.peek());
        stack.push(nums2[i]);
    }
    int[] result = new int[nums1.length];
    for(int i=0;i<nums1.length;i++){
        result[i] = map.get(nums1[i]);
    }
    return result;
}




/**
     * 因为要求更大元素，建立一个从栈底到栈顶由大到小的栈.
     * 当某个元素大于栈顶元素，将栈顶元素弹出，而该元素就是栈顶元素的最右侧的第一个大于它的元素。
     * 而要是求最左侧的最大元素，那么，某个元素在栈中的下一个元素就是大于它的第一个元素。
     * */
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer,Integer> map = new HashMap<>();
    Stack<Integer> statck = new Stack<>();
    for(int i=0;i<nums2.length;i++){
        while(!statck.isEmpty()&&nums2[statck.peek()]<nums2[i]){
            int index = statck.pop();
            map.put(nums2[index],nums2[i]);
        }
        statck.push(i);
    }
    while(!statck.isEmpty()){
        map.put(nums2[statck.pop()],-1);
    }
    int[] res = new int[nums1.length];
    for(int i=0;i<nums1.length;i++){
        res[i] = map.get(nums1[i]);
    }
    return res;
}

/**给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），
     * 输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，
     * 这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。
     * 如果不存在，则输出 -1。
     *
     * 关于环型数组的问题，构建一个环型数组可以通过取余运算来解决
     * 例如，[1,3,4,2]，我们将其当作[1,3,4,2,1,3,4,2]来看待，遍历这个2n长度的数组
     * 其他的，与之前的求下一个最大元素类似，使用单调栈来解决
     * */
public int[] nextGreaterElements(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    int[] result = new int[nums.length];
    int length = nums.length;
    for(int i = 2*nums.length-1;i>=0;i--){
        while(!stack.isEmpty()&&stack.peek()<=nums[i%length]){
            stack.pop();
        }
        result[i%length] = stack.isEmpty()?-1:stack.peek();
        stack.push(nums[i%length]);
    }
    return result;
}

 public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i<nums.length*2;i++){
            while(!stack.isEmpty()&&nums[i%n]>nums[stack.peek()%n]){
                int index = stack.pop()%n;
                res[index%n] = nums[i%n];
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int index = stack.pop();
            if(index<nums.length){
                res[index] = -1;
            }
        }
        return res;
    }

 /**
     * 给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，
     * 并且其值大于n。如果不存在这样的32位整数，则返回-1。
     *1.寻找第一个不是单调减的元素i，假如没有，返回-1
     * 2.寻找大于i的最小元素
     * 3.交换两个元素
     * 4.将i之后的元素反置
     * */
public int nextGreaterElement(int n) {
    char[] a = (""+n).toCharArray();
    if(a.length<2){
        return -1;
    }
    //从尾部寻找第一个不是递减的元素
    int index = a.length-2;
    while(index>=0&&a[index+1]<=a[index]){
        index--;
    }
    if(index<0){
        return -1;
    }
    int j = a.length-1;
    //寻找大于a[index]的
    while(j>index&&a[index]>=a[j]){
        j--;
    }
    swap(a,index,j);
    reverse(a,index+1,a.length-1);
    //注意处理异常，可能会溢出int范围
    try {
        return Integer.parseInt(new String(a));
    }catch(Exception e){
        return -1;
    }
}
public void swap(char[] a,int i,int j){
    char tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

public void reverse(char[] a,int i,int j){
    while(i<j){
        swap(a,i,j);
        i++;
        j--;
    }
}

/**
     * 每日温度
     * 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。
     * 如果之后都不会升高，请在该位置用 0 来代替。
     *
     *单调递增栈来解决
     * */
public int[] dailyTemperatures(int[] T) {
    Stack<Integer> stack = new Stack<>();
    int[] res = new int[T.length];
    for(int i=0;i<T.length;i++){
        while(!stack.isEmpty()&&T[i]>T[stack.peek()]){
            int index = stack.pop();
            res[index] = i-index;
        }
        stack.push(i);
    }
    while(!stack.isEmpty()){
        int index = stack.pop();
        res[index] = 0;
    }
    return res;
}

/**
 * 今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
 * 其实就是求最近的大于他的元素
 * */
public class StockSpanner {
    Stack<Integer> prices = new Stack<>();
    Stack<Integer> weights = new Stack<>();
    public StockSpanner() {

    }

    public int next(int price) {
        int weight = 1;
        while(!prices.isEmpty()&&prices.peek()<=price){
            prices.pop();
            weight+=weights.pop();
        }
        prices.push(price);
        weights.push(weight);
        return weight;
    }
}

//本质就是找到某个元素左侧第一个小于它的元素，以及右侧小于它的第一个元素
public int largestRectangleArea(int[] nums) {
    if(nums.length==0){
        return 0;
    }
    Stack<Integer> stack = new Stack<>();
    int max = 0;
    for(int i =0;i<nums.length;i++){
        while(!stack.isEmpty()&&nums[i]<nums[stack.peek()]){
            int ele = stack.pop();
            int after_index = i;
            int before_index = stack.isEmpty()?-1:stack.peek();
            max = Math.max(max,(after_index-before_index-1)*nums[ele]);
        }
        stack.push(i);
    }

    while(!stack.isEmpty()){
        int after_index = nums.length;
        int ele = stack.pop();
        int before_index =  stack.isEmpty()?-1:stack.peek();
        max = Math.max(max,(after_index-before_index-1)*nums[ele]);
    }
    return max;
}

/**
     * 单调栈的应用
     * 对于某一个数组[3,2,4,2],求他形成的最大的最大矩形面积
     * 例如，对3，求其两侧的第一个小于它的元素，这两者之间的距离即是可以形成的矩形
     * */
public int maximalRectangle(char[][] matrix) {
    int max = 0;
    if(matrix.length==0||matrix[0].length==0){
        return max;
    }
    int[] helper = new int[matrix[0].length];
    for(int i=0;i<matrix.length;i++){
        for(int j =0;j<matrix[0].length;j++){
            if(String.valueOf(matrix[i][j]).equals("0")){
                helper[j] = 0;
            }else{
                helper[j]++;
            }
        }
        max = Math.max(max,generateMatrixArea(helper));
    }
    return max;
}
//本质就是找到某个元素左侧第一个小于它的元素，以及右侧小于它的第一个元素
public int generateMatrixArea(int[] nums){
    Stack<Integer> stack = new Stack<>();
    int max = Integer.MIN_VALUE;
    for(int i =0;i<nums.length;i++){
        while(!stack.isEmpty()&&nums[i]<nums[stack.peek()]){
            int ele = stack.pop();
            int after_index = i;
            int before_index = stack.isEmpty()?-1:stack.peek();
            max = Math.max(max,(after_index-before_index-1)*nums[ele]);
        }
        stack.push(i);
    }

    while(!stack.isEmpty()){
        int after_index = nums.length;
        int ele = stack.pop();
        int before_index =  stack.isEmpty()?-1:stack.peek();
        max = Math.max(max,(after_index-before_index-1)*nums[ele]);
    }
    return max;
}

//使用单调递减栈，假如某个元素大于栈顶元素，因为元素栈底到栈顶是由大到小的，所以必定可以形成雨水区域
public int trap(int[] height) {
    if(height.length<3){
        return 0;
    }
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    for(int i=0;i<height.length;i++){
        while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
            int top = stack.pop();
            if(stack.isEmpty()){
                break;
            }
            //计算雨水区域大小,注意是i-stack.peek()-1，不是i-top
            res+=(i-stack.peek()-1)*(Math.min(height[i],height[stack.peek()])-height[top]);
        }
        stack.push(i);
    }
    return res;
}

 /**
     * 双端队列
     * 队头永远存储最大值，双端队列是单调递减的。
     * 入队的时候，假如<队尾元素,直接入队,假如>=队尾元素，那么将队尾元素挤掉，直到<队尾元素
     * 还需要注意的是，需要对队头元素是否过期进行判断：i-w==queue.peekFirst()
     * */
public int[] maxSlidingWindow(int[] nums, int k) {
    if(nums.length<k||nums.length<1){
        return new int[0]; 
    }
    //队列中存储的是下标
    LinkedList<Integer> queue = new LinkedList<>();
    int[] res = new int[nums.length-k+1];
    int index = 0;
    for(int i=0;i<nums.length;i++){
        //假如>=队尾元素，那么将队尾元素挤掉，直到<队尾元素
        while(!queue.isEmpty()&&nums[i]>=nums[queue.peekLast()]){
            queue.pollLast();
        }
        //元素入队
        queue.addLast(i);
        //过期判定
        if(i-k==queue.peekFirst()){
            queue.pollFirst();
        }
        //窗口中至少有k个元素，求取最值
        if(i>=k-1){
            res[index++] = nums[queue.peekFirst()];
        }
    }
    return res;
}

/**
     * 准备两个单调队列，一个单调递减，存储的是最大值，一个单调递增，存储的是最小值
     * 假如[L,R]区间内满足max-min<=target，那么[L,L..R]中也必定满足；假如[L,R]区间内不满足max-min<=target，那么[L,R.R+1...arr.length]中也必定不满足；
     * */
public int SubArray(int[] nums,int target){
    //单调减队列，队头存储的是最大值
    LinkedList<Integer> qmax = new LinkedList<>();
    //单调增队列，队头存储的是最小值
    LinkedList<Integer> qmin = new LinkedList<>();
    int left = 0;
    int right = 0;
    int res = 0;
    while(left<nums.length){
        //构建单调队列，假如nums[qmax.peekFirst()]-nums[qmin.peekFirst()]>target，表明以left开始，只有[left,left.....right)这些个子数组是符合条件的
        while(right<nums.length){
            while(qmax.size()>0&&nums[qmax.peekLast()]<=nums[right]){
                qmax.pollLast();
            }
            qmax.push(right);
            while(qmin.size()>0&&nums[qmin.peekLast()]>=nums[right]){
                qmin.pollLast();
            }
            qmin.push(right);
            if(nums[qmax.peekFirst()]-nums[qmin.peekFirst()]>target){
                break;
            }
            right++;
        }

        //过期条件，因为需要将left右移，所以，下标为left的队列元素应该删除
        if(qmax.peekFirst()==left){
            qmax.pollFirst();
        }
        if(qmin.peekFirst()==left){
            qmin.pollFirst();
        }
        res+=right-left;
        left++;
    }
    return res;
}

string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right++]);
    // 如果符合要求，移动 left 缩小窗口
    while (window 符合要求) {
        // 如果这个窗口的子串更短，则更新 res
        res = minLen(res, window);
        window.remove(s[left++]);
    }
}
return res;

/**
     *需要准备两个指针，left以及right，将right不断右移，直到[left...right]包含了t，那么这是一个满足条件的子数组
     * 但是，还有可能更短，将left右移动，直到[left...right]依旧包含t，当[left...right]不包含t的时候left移动停止
     * 再将right右移，重复以上过程
     * */
public String minWindow(String s, String t) {
    if(s==null||t==null||s.length()<t.length()){
        return "";
    }
    //存储欠的字符的个数,例如t="abc"，那么初始应该前a:1,b:1,c:1
    int[] map = new int[256];
    for(int i=0;i<t.length();i++){
        map[t.charAt(i)]++;
    }
    //还差多少个字符串才能包含t，初始为t的长度，当match==0时，表明已经包含了t
    int match = t.length();
    int left = 0;
    int right = 0;
    int min = Integer.MAX_VALUE;
    String res="";
    while(right<s.length()){
        map[s.charAt(right)]--;
        //假如某个字符的map>=0，match--
        if(map[s.charAt(right)]>=0){
            match--;
        }
        //假如match==0，表明找到了一个子数组;但有可能该子数组并不是最短的，因此，应该将left左移，假如移动过程中有一个字符欠元素了，left停止移动
        if(match==0){
            while(map[s.charAt(left)]<0){
                map[s.charAt(left++)]++;
            }
            if(min>right-left+1){
                min = right-left+1;
                //beginIndex - 开始处的索引（包括）endindex 结尾处索引（不包括）
                res = s.substring(left,right+1);
            }
            match++;
            map[s.charAt(left++)]++;
        }
        right++;
    }
    return res;
}

public int lengthOfLongestSubstring(String s) {
    int left = 0;
    int right = 0;
    int max = 0;
    //记录字符出现的次数
    int[] map = new int[256];
    while(right<s.length()){
        char c1 = s.charAt(right);
        map[s.charAt(right++)]++;
        while(map[c1]>1){
            map[s.charAt(left++)]--;
        }
        max = Math.max(max,right-left);
    }
    return max;
}

/**
 * 需要准备一个map，一个双向链表，双向链表来解决访问记录的问题 .hashMap来存储数据。
 * 双向链表来存储数据访问的先后顺序，头节点代表的就是最久未访问的数据
 * 双向链表中存储的节点包含key以及value
 * 添加元素时，需要将node插入到双向链表以及map中，而且，假如插入的key以及包含了，那么代表该点被访问了，需要将其移动到双向链表尾部；当添加元素大于容量，需要将双向链表头部元素以及map中相应元素删除
 * 当访问某一个元素时，需要将该元素移动到链表尾部
 * */
public class LRUCache {
    //双链表中的数据节点，存储的是key
    public class Node{
        public int key;
        public int value;
        public Node pre;
        public Node next;
        Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
    //定义双链表
    public class DoubleList{
        private Node head;
        private Node tail;
        public DoubleList(){
            this.head=null;
            this.tail=null;
        }
        public void addNode(Node node){
            if(node==null){
                return ;
            }
            if(this.head==null){
                head = node;
                tail = node;
            }else{
                tail.next = node;
                node.pre = tail;
                tail = node;
            }
        }

        //将某个节点移动到尾部，即将访问过的节点移动到尾部
        public void moveToTail(Node node){
            if(tail==node){
                return;
            }
            if(head==node) {
                head.next.pre = null;
                head = head.next;
            }else{
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            tail.next = node;
            node.pre = tail;
            tail = node;
            node.next = null;
        }
        //删除头节点
        public Node removeHead(){
            if(head==null){
                return null;
            }
            Node tmp = head;
            if(head==tail){
                head=null;
                tail=null;
            }else {
                head.next.pre = null;
                head = head.next;
                tmp.next = null;
            }
            return tmp;
        }
    }
    Map<Integer,Node> map = new HashMap<>();
    DoubleList list = new DoubleList();
    private int capicity;
    public LRUCache(int capacity) {
        this.capicity = capacity;
    }

    public int get(int key) {
        //map中含有该元素，直接获取value，并将节点移动至尾部
        if(map.containsKey(key)){
            list.moveToTail(map.get(key));
            return map.get(key).value;
        }else{
            return -1;
        }
    }

    public void put(int key, int value) {
        //map中包含该元素，那么更新value，并将list中节点移动到队尾
        if(map.containsKey(key)){
            map.get(key).value = value;
            list.moveToTail(map.get(key));
        }else{
            //map中没有该元素，新建节点直接插入map，并且插入到list尾部,假如超过了容量，需要list头部元素删除，并且删除map中相应元素
            Node node = new Node(key,value);
            map.put(key,node);
            list.addNode(node);
            if(map.size()==size+1){
                removeHead();
            }
        }
    }

    //删除list头部元素以及map中相应元素
    public void removeHead(){
        Node node = list.deleteHeadNode();
        map.remove(node.key);
    }
}