class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<Integer>();
        if (matrix.length == 0) {
            return ans;
        }
        int R = matrix.length, C = matrix[0].length;
        boolean[][] seen = new boolean[R][C];
        int[] dr = {0, 1, 0, -1}; //横向如果是顺时针的话坐标，先不变，在加， 在不变，在减去
        int[] dc = {1, 0, -1, 0};
        int r = 0, c = 0, di = 0;
        for (int i = 0; i < R * C; i++) {
            ans.add(matrix[r][c]);
            seen[r][c] = true;
            int cr = r + dr[di];
            int cc = c + dc[di];
            if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]) {
                r = cr;
                c = cc;
            } else {
                //这说明碰到了墙壁，要折行了
                di = (di + 1) % 4;
                r += dr[di];
                c += dc[di];
            }
        }
        return ans;

    }
}

class MYQueue {
    private List<Integer> data;
    private int p_start;
    public MyQueue() {
        data = new ArrayList<Integer>();
        p_start = 0;
    }

    public boolean enQueue(int x) {
        data.add(x);
        return true;
    }

    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        p_start++;
        return true;
    }

    public int Front() {
        return data.get(p_start);
    }

    public boolean isEmpty() {
        return p_start >= data.size();
    }
}

class MyCircularQueue {
    int data[];
    int p_start;
    int p_end;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        data = new int[k];
        p_start = -1;
        p_end = -1;
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        } else {
            if (p_start == -1) {
                p_start = 0;
            }
            p_end = (p_end + 1) % (data.length);
            data[p_end] = value;
            return true;
        }
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        int y;
        if (isEmpty()) {
            return false;
        } else {
            y = data[p_start];
            if (p_start == p_end) {
                p_start = -1;
                p_end = -1;
            } else {
                p_start = (p_start + 1) % data.length;
            }
            return true;
        }
    }

    /** Get the front item from the queue. */
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[p_start];
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data[p_end];
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        if (p_start == -1) {
            return true;
        }
        return false;
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        if(p_start  == 0 && p_end == data.length - 1) {
            return true;
        }
        if (p_start == p_end + 1) {
            return true;
        }
        return false;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

/**
 * 返回根结点到目标结点的最短路径
 */
int BFS(Node root, Node target) {
    Queue<Node> queue; //保存所有待处理的所有结点
    int step = 0; //从根结点到当前结点的步数
    //初始化
    add root to queue;
    while (queue is not empty) {
        step = step + 1;
        //遍历在队列总的结点
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = this first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;

}

int BFS(Node root, Node target) {
    Queue<Node> queue;
    Set<Node> used; //保存所有已经使用过的结点
    int step = 0;
    //初始化
    add root to queue;
    add root to used;
    //BFS
    while (queue is not empty) {
        step = step + 1;
        int size = queue.size();
        for (int i = 0； i < size; ++i) {
            Node cur = this first node in queue;
            return step if cur is target;
            for (Node next : this neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;

}

class MyStack {
    private List<Integer> data;
    public MyStack() {
        data = new ArrayList<>();
    }

    public void push(int x) {
        data.add(x);
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    public int top() {
        return data.get(data.size() - 1);
    }

    public boolean pop() {
        is(isEmpty()) {
            return false;
        }
        data.remove(data.size() - 1);
        return true;
    }
}

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        // 单调栈 里面的数 非递增排序 
        Stack<Integer> stack = new Stack();
        // 从后往前遍历
        for(int i = T.length-1; i >= 0; i--){
            // 当前元素比栈顶元素大 出栈 重新调整栈直至满足要求
            while(!stack.isEmpty() && T[i] >= T[stack.peek()]){
                stack.pop();
            }
            // 栈为空 即后面没有比当前天温度高的
            // 不为空 栈顶元素对应的下标减去当前下标即为经过几天后温度比当前天温度高
            res[i] = stack.isEmpty()? 0 :stack.peek()-i;
            // 当前元素进栈
            stack.push(i);
        }
        return res;
    }
}