[Note] Matrix

Posted by 西维蜀黍的OJ Blog on 2023-09-10, Last Modified on 2025-04-16

解析

54. Spiral Matrix

    # - time: O(m*n)
    # - space: O(m*n) -> O(1) extra space, and O(m*n) space for the output list
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        # current valid search range: col: [minCol, maxCol], row: [minRow, maxRow]
        # this means that "while minRow <= maxRow and minCol <= maxCol"
        minRow, maxRow = 0, len(matrix) - 1
        minCol, maxCol = 0, len(matrix[0]) - 1

        res = []
        while minRow <= maxRow and minCol <= maxCol:
            # get every element in the top row
            for c in range(minCol, maxCol + 1):
                res.append(matrix[minRow][c])
            minRow += 1  # to exclude the min row

            # get every element in the right col
            for r in range(minRow, maxRow + 1):
                res.append(matrix[r][maxCol])
            maxCol -= 1

            # [[1,2,3]] or [[1], [2], [3]]
            # minCol > maxCol 说明没有任何 col 可以再被考虑了
            # minRow > maxRow 说明没有任何 row 可以再被考虑了
            # 所以如果满足任何条件,直接跳出
            if minCol > maxCol or minRow > maxRow:
                break

            # get every element in the bottom row
            for c in range(maxCol, minCol - 1, -1):
                res.append(matrix[maxRow][c])
            maxRow -= 1

            # get every element in the left col
            for r in range(maxRow, minRow - 1, -1):
                res.append(matrix[r][minCol])
            minCol += 1

        return res

ref