题目描述

Given an m * n matrix M initialized with all 0's and several update operations.

Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.

You need to count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.

Note:

  1. The range of m and n is [1,40000].
  2. The range of a is [1,m], and the range of b is [1,n].
  3. The range of operations size won't exceed 10,000.

解法一

思路

注意到这里虽然是指定矩形的某一范围内数字全部增加1，但矩形的左上角顶点永远都是(0, 0)，如下图所示。

Range Addition

想要求得最大数的个数，也就是要确定哪块区域是所有的矩形都覆盖到了的，从上图我们可以显然发现，面积最小的那块矩形是所有矩形都覆盖到了的，所以这题实际就是确定最小的那个矩形了，这个简单，找到最小的长和宽就好了。

Python

class Solution:
    def maxCount(self, m, n, ops):
        """
        :type m: int
        :type n: int
        :type ops: List[List[int]]
        :rtype: int
        """
        result_m = m
        result_n = n
        for op in ops:
            result_m = min(result_m, op[0])
            result_n = min(result_n, op[1])
        return result_m * result_n

Java

public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int resultM = m;
        int resultN = n;
        for (int[] op : ops) {
            resultM = Math.min(resultM, op[0]);
            resultN = Math.min(resultN, op[1]);
        }
        return resultM * resultN;
    }
}

C++

class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>> &ops) {
        int resultM = m;
        int resultN = n;
        for (const vector<int> &op : ops) {
            resultM = min(resultM, op[0]);
            resultN = min(resultN, op[1]);
        }
        return resultM * resultN;
    }
};