剑指 Offer 29. 顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
依次模拟从左到右、从上到下、从右到左、从下到上的遍历过程，实现从外到里以顺时针完成矩阵遍历

代码实现 

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        int m = matrix.length;
        if(m == 0){
            return new int[0];
        }
        int n = matrix[0].length;
        int[] res = new int[m * n];
        int index = 0;
        int left = 0;
        int right = n - 1;
        int top = 0;
        int buttom = m - 1;
        while(left <= right && top <= buttom){
            for(int i = left; i <= right; i++){ //从左到右
                res[index++] = matrix[top][i];
            }
            top++;
            for(int i = top; i <= buttom; i++){ //从上到下
                res[index++] = matrix[i][right];
            }
            right--;
            for(int i = right; i >= left && top <= buttom; i--){ //从右到左
                res[index++] = matrix[buttom][i];
            }
            buttom--;
            for(int i = buttom; i >= top && left <= right; i--){ //从下到上
                res[index++] = matrix[i][left];
            }
            left++;
        }
        return res;
    }
}

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

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
输入：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
🔗题目链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof

思路

根据出栈序列可以确定哪些元素需要先入栈，如上面示例给出的出入栈序列，第一个出栈元素为4，则可根据入栈序列依次入栈1，2，3，直到遇到该出栈元素，此时可说明该元素的出栈顺序是正确的，接着确定下一个出栈元素，若此时该出栈元素等于当前栈的栈顶元素就直接出栈，以此类推；
当遍历完入栈序列时，此时已完成了入栈，需依次将栈中元素出栈与出栈序列中的元素比较，不同直接返回false。

代码实现 

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int length = pushed.length;
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < length; i++){
            int k = popped[i]; //确定当前的出栈元素
            if(!stack.empty() && k == stack.peek()){ 
                //当前出栈元素等于栈顶元素就出栈
                stack.pop();
                continue;
            }
            while(j < length && pushed[j] != k){ 
                //根据入栈序列依次入栈，直到遇到当前的出栈元素
                stack.push(pushed[j]);
                j++;
            }
            if(j >= length && stack.pop() != k){
                //若此时已完成入栈，判断出栈序列是否相同
                return false;
            }else{
                j++;
            }
        }
        return true;
    }
}