54. Spiral Matrix

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

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

🧠 Thuật Toán & Kỹ Thuật

Bit Manipulation (Thao tác bit)Matrix (Ma trận)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

C++ 0054-spiral-matrix.cpp 
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int u = 0, d = m - 1, l = 0, r = n - 1;
        
        vector<int> ans;
        
        while (u <= d and l <= r) {
            for (int col = l; col <= r; ++col) {
                ans.push_back(matrix[u][col]);
            }
            u++;
            if (u > d) {
                break;
            }
            for (int row = u; row <= d; ++row) {
                ans.push_back(matrix[row][r]);
            }
            r--;
            if (r < l) {
                break;
            }
            for (int col = r; col >= l; --col) {
                ans.push_back(matrix[d][col]);
            }
            d--;
            if (d < u) {
                break;
            }
            for (int row = d; row >= u; --row) {
                ans.push_back(matrix[row][l]);
            }
            l++;
            if (l > r) {
                break;
            }
        }
        
        return ans;
    }
};