Leetcode : 598 .範囲追加

問題声明
あなたはすべての0と初期化された操作の配列で初期化されたM x N行列Mを与えられます、そして、Op [ i ] = [ ai , bi ]はM [ x ] [ y ]がすべての0 <= x < aiと0 <= y < biのために1で増分されることを意味します.
すべての操作を実行した後、行列の最大整数数をカウントして返します.

Example 1:
Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

Example 2:
Input: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
Output: 4

Example 3:
Input: m = 3, n = 3, ops = []
Output: 9

制約

1 <= m , n <= 4 * 104

1 = OPS.長さ<> 104

OPS [ I ]長さ＝2

1 <= ai <= M

1 <= bi <= n

考え

The problem statement says that we will be given a matrix and an array of matrix cell positions , we need to increment the count of all the cells from (0,0) to each matrix cell position. After completing all these operations we need to find out the count of maximum integer in the matrix.

So , the question is to find out the count of the maximum integer after performing all the given operations.

As per the question , a cell (x , y) value can be incremented if and only if (x , y) is one of the cell from (0,0) to the given input (p , q).

So , the maximum integer will be produced when matrix cell value is incremented more number of times.

For a matrix cell to be maximum value , we need to figure out the most overlapping cell between the given set of operations/matrix cell positions as the range of cells which overlaps the most will get chance to increment more number of times.

If you look at the first example , in first operation each cell value is incremented from (0,0) to (2,2) , in second operation each cell from (0,0) to (2,2) again got incremented as it overlaps with (3,3).

So , solution is to simple find out the product of minimum of first co-ordinates of cell and minimum of second co-ordinates of cell.

We are taking product because we need to find out the count of the maximum integer in the matrix after performing all the given operations.

コードパイソン

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        length = len(ops)
        if length == 0:
            return m*n
        result = [ops[0][0] , ops[0][1]]
        for i in range(1,length):
            result[0] = min(result[0] , ops[i][0])
            result[1] = min(result[1] , ops[i][1])
        return result[0]*result[1]        

Link to the question on leetcode
git repoの下にはいくつかの重要なプログラミングの質問とソリューションleetcodeとinterviewbit

dheerajthodupunoori / problem-solving
問題解決の質問と解決.
問題解決
このリポジトリには重要なデータ構造とアルゴリズムの質問のいくつかが含まれています.
現在、このリポジトリにはグラフデータ構造とリンクリストに関する質問がいくつか含まれています.よりすぐに追加されます.
このリポジトリに貢献してください.
View on GitHub