54. 螺旋矩阵(Spiral Matrix)M

英文题目

• Given an m x n matrix, return all elements of the matrix in spiral order.

• Example 1:

• 

• Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
  Output: [1,2,3,6,9,8,7,4,5]
  

• Example 2:

• 

• Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
  Output: [1,2,3,4,8,12,11,10,9,5,6,7]
  

• Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

中文题目

• 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

• 示例 1：

• 

• 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
  输出：[1,2,3,6,9,8,7,4,5]
  

• 示例 2：

• 

• 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
  输出：[1,2,3,4,8,12,11,10,9,5,6,7]
  

• 提示：

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

模拟

• 就只需要定义上下左右的边界，然后在边界上迭代即可

• 时间复杂度O(mn)，空间复杂度O(1)

  # python3: 时间 36 ms, 击败 85.49%; 内存 15.9 MB, 击败 65.19%
  class Solution:
      def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
          res = []
          if not matrix:
              return res
          top, down = 0, len(matrix) - 1
          left, right = 0, len(matrix[0]) - 1
          while True:
              # 顶上从左到右
              for i in range(left, right + 1):
                  res.append(matrix[top][i])
              top += 1
              if top > down: 
                  break
              
              # 右边从上到下
              for i in range(top, down + 1):
                  res.append(matrix[i][right])
              right -= 1
              if left > right:
                  break
              
              # 下边从右到左
              for i in range(right, left - 1, -1):
                  res.append(matrix[down][i])
              down -= 1
              if top > down:
                  break
              
              # 左边从下到上
              for i in range(down, top - 1, -1):
                  res.append(matrix[i][left])
              left += 1
              if left > right:
                  break
          return res
  

  // c++: 时间 4 ms, 击败 33.12%; 内存 6.7 MB, 击败 38.52%
  class Solution {
  public:
      vector<int> spiralOrder(vector<vector<int>>& matrix) {
          vector<int> res;
          if (matrix.empty()) {
              return res;
          }
          int top = 0, down = matrix.size() - 1;
          int left = 0, right = matrix[0].size() - 1;
          while (true) {
              for (int i = left; i <= right; ++i) {
                  res.push_back(matrix[top][i]);
              }
              ++top;
              if (top > down) {
                  break;
              }
  
              for (int i = top; i <= down; ++i) {
                  res.push_back(matrix[i][right]);
              }
              --right;
              if (left > right) {
                  break;
              }
  
              for (int i = right; i >= left; --i) {
                  res.push_back(matrix[down][i]);
              }
              --down;
              if (top > down) {
                  break;
              }
  
              for (int i = down; i >= top; --i) {
                  res.push_back(matrix[i][left]);
              }
              ++left;
              if (left > right) {
                  break;
              }
          }
          return res;
      }
  };
  

  // java: 时间 0 ms, 击败 100%; 内存 39.5 MB, 击败 73.53%
  class Solution {
      public List<Integer> spiralOrder(int[][] matrix) {
          List<Integer> res = new ArrayList<>();
          if (matrix.length == 0) {
              return res;
          }
          int top = 0, down = matrix.length - 1;
          int left = 0, right = matrix[0].length - 1;
          while (true) {
              for (int i = left; i <= right; ++i) {
                  res.add(matrix[top][i]);
              }
              ++top;
              if (top > down) {
                  break;
              }
  
              for (int i = top; i <= down; ++i) {
                  res.add(matrix[i][right]);
              }
              --right;
              if (left > right) {
                  break;
              }
  
              for (int i = right; i >= left; --i) {
                  res.add(matrix[down][i]);
              }
              --down;
              if (top > down) {
                  break;
              }
  
              for (int i = down; i >= top; --i) {
                  res.add(matrix[i][left]);
              }
              ++left;
              if (left > right) {
                  break;
              }
          }
          return res;
      }
  }
  

  // go: 时间 0 ms, 击败 100%; 内存 1.8 MB, 击败 59.96%
  func spiralOrder(matrix [][]int) []int {
      res := []int{}
      if len(matrix) == 0 {
          return res
      }
      top, down := 0, len(matrix) - 1
      left, right := 0, len(matrix[0]) - 1
      for {
          for i := left; i <= right; i++ {
              res = append(res, matrix[top][i])
          }
          top++
          if top > down {
              break
          }
  
          for i := top; i <= down; i++ {
              res = append(res, matrix[i][right])
          }
          right--
          if left > right {
              break
          }
  
          for i := right; i >= left; i-- {
              res = append(res, matrix[down][i])
          }
          down--
          if top > down {
              break
          }
  
          for i := down; i >= top; i-- {
              res = append(res, matrix[i][left])
          }
          left++
          if left > right {
              break
          }
      }
      return res
  }
  

  // javascript: 时间 48 ms, 击败 98.25%; 内存 40.9 MB, 击败 40.51%
  /**
   * @param {number[][]} matrix
   * @return {number[]}
   */
  var spiralOrder = function(matrix) {
      const res = new Array();
      if (!matrix.length) {
          return res;
      }
      let top = 0, down = matrix.length - 1;
      let left = 0, right = matrix[0].length - 1;
      while (true) {
          for (let i = left; i <= right; ++i) {
              res.push(matrix[top][i]);
          }
          ++top;
          if (top > down) {
              break;
          }
  
          for (let i = top; i <= down; ++i) {
              res.push(matrix[i][right]);
          }
          --right;
          if (left > right) {
              break;
          }
  
          for (let i = right; i >= left; --i) {
              res.push(matrix[down][i]);
          }
          --down;
          if (top > down) {
              break;
          }
  
          for (let i = down; i >= top; --i) {
              res.push(matrix[i][left]);
          }
          ++left;
          if (left > right) {
              break;
          }
      }
      return res;
  };