LeetCodeを1日1題解いてみる (day48)

48日目に取り組んだ問題はこちら！

598. Range Addition II

問題文

You are given an m x n matrix M initialized with all 0's and an array of operations ops, where ops[i] = [ai, bi] means M[x][y] should be incremented by one for all 0 <= x < ai and 0 <= y < bi.

Count and return the number of maximum integers in the matrix after performing all the operations.

僕の回答 (失敗作)

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        M = [[0] * n for _ in range(m)]
        if not ops:
            return m * n
        for oper in ops:
            a, b = oper
            for i in range(a):
                for j in range(b):
                    M[i][j] += 1
        max_val = None
        max_count = 0
        for i in range(m):
            temp = max(M[i])
            if not max_val or temp > max_val:
                max_val = temp
                max_count = 0
            if max_val == temp:
                max_count += M[i].count(max_val)
        
        return max_count

Memory Limit Exceededで失敗で終わってしまった。

回答例

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        if not ops:
            return m * n

        # 操作の行数と列数の最小値を求める
        min_row = min(op[0] for op in ops)
        min_col = min(op[1] for op in ops)

        # 最大値が存在する領域の面積
        return min_row * min_col

学んだこと

M = [[0] * n] * mは、0がn個ある配列をm行分作って初期化するという意味だと思っていたが、実際には、[[0] * n] のリストへの参照がm回複製されるという意味だった。

コメント

僕は丁寧に１つずつ計算してそこから最大値を探して最大値の個数を数えるという平凡な案しか思いつかなかったが、回答例は美しい解法でびっくりしました。柔軟に考えられるようになりたいです。

次の問題はこちら!