598. 范围求和 II （脑筋急转弯）

给你一个 m x n 的矩阵 M ，初始化时所有的 0 和一个操作数组 op ，其中 ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， M[x][y] 应该加 1。

在 执行完所有操作后 ，计算并返回 矩阵中最大整数的个数 。

---

输入: m = 3, n = 3，ops = [[2,2],[3,3]]
输出: 4
解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。

1
2
3
4

---

【思路】：
本题如果去用常规思路，建立一个二维数组去算是不能通过的，最后m和n的数据量会很大，导致超时。

本题其实跟算法没什么关系，考验从另一个角度巧解问题。

实际上这个问题可以转化成：求左上角重叠的最小矩形。
因为我们知道最大值肯定取在左上角。

比如[2,2], [3, 3]这个测试用例：
左上角最后形成的最小矩形面积为2*2 = 4，正是由[2,2]带来的，跟[3,3]一点关系都没有。

再比如[3,2]， [2,3]这个测试用例：
最后经过重叠交叉之后，形成的最小矩形面积也是[2,2]，所以肯定也是4

那么思路就很明显了，就是对ops进行排序。取出行最小的行和最小的列，两者一乘即为最后结果。

---

【代码】
对行列分别排序

var maxCount = function(m, n, ops) {
    if(!ops.length) return m * n;
    let row = [];
    let col = [];
    for(let i = 0; i<ops.length; i++){
        row.push(ops[i][0]);
        col.push(ops[i][1]);
    };
    row.sort((a,b)=> a-b);
    col.sort((a,b)=> a-b);
    return row[0] * col[0]
};
1
2
3
4
5
6
7
8
9
10
11
12