剑指 Offer 29. 顺时针打印矩阵 & 31. 栈的压入、弹出序列

29题目描述：

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

解析：

1.如果数组为空，则返回空数组
2.定义四个边界及当前方向
3.当左边界小于等于右边界，且上边界小于等于下边界时，执行while循环：
按照右、下、左、上的顺序，依次将路径上的字符添加到结果里
4.while循环结束后，返回结果

Java:

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
        int m = matrix.length, n = matrix[0].length, num = 0;
        int[] res = new int[m * n];
        String direction = "right";
        while(left <= right && top <= bottom) {
            if(direction == "right") {
                for(int i = left; i <= right; i++) {
                    res[num++] = matrix[top][i];
                }
                top++;
                direction = "down";
            } else if(direction == "down") {
                for(int i = top; i <= bottom; i++) {
                    res[num++] = matrix[i][right];
                }
                right--;
                direction = "left";
            } else if(direction == "left") {
                for(int i = right; i >= left; i--) {
                    res[num++] = matrix[bottom][i];
                }
                bottom--;
                direction = "top";
            } else if(direction == "top") {
                for(int i = bottom; i >= top; i--) {
                    res[num++] = matrix[i][left];
                }
                left++;
                direction = "right";
            }
        }
        return res;
    }
}

JavaScript:

var spiralOrder = function(matrix) {
    if(matrix === null || matrix.length === 0 || matrix[0].length === 0) {
        return [];
    }
    let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
    let res = [];
    let direction = "right";
    while(left <= right && top <= bottom) {
        if(direction === "right") {
            for(let i = left; i <= right; i++) {
                res.push(matrix[top][i]);
            }
            top++;
            direction = "down";
        } else if(direction === "down") {
            for(let i = top; i <= bottom; i++) {
                res.push(matrix[i][right]);
            }
            right--;
            direction = "left";
        } else if(direction === "left") {
            for(let i = right; i >= left; i--) {
                res.push(matrix[bottom][i]);
            }
            bottom--;
            direction = "top";
        } else if(direction === "top") {
            for(let i = bottom; i >= top; i--) {
                res.push(matrix[i][left]);
            }
            left++;
            direction = "right";
        }
    }
    return res;
};

31题目描述：

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

解析：

1.判断合不合法，用个栈试一试
2.把压栈的元素按顺序压入，当栈顶元素和出栈的第一个元素相同，则将该元素弹出，出栈列表指针后移并继续判断
3.最后判断出栈列表指针是否指向出栈列表的末尾即可

Java:

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for(int i = 0; i < popped.length; i++) {
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek() == popped[index]) {
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}

JavaScript:

var validateStackSequences = function(pushed, popped) {
    if(pushed.length === 0 || popped.length === 0) {
        return true;
    }
    let stack = [];
    let index = 0;
    for(let i = 0; i < popped.length; i++) {
        stack.unshift(pushed[i]);
        while(stack.length && stack[0] === popped[index]) {
            stack.shift();
            index++;
        }
    }
    return (stack.length === 0);
};