LeetCode算法题-Range Addition II（Java实现）

佚名 5年前 (2019-03-09) 算法 1424人围观抢沙发百度已收录

这是悦乐书的第271次更新，第285篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第138题（顺位题号是598）。给定一个m行n列的新二维数组M，其初始值为0。提供一个二维数组ops，每次对M做如下操作，每次从ops中取出一个数组temp，temp里面包含两个整数a和b，使得M[i][j]的元素都自增1，其中0 <= i < a， 0 <= j < b。在遍历完ops中的所有数组后，找出M中值最大的元素的个数。例如：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入: m = 3, n = 3，ops = [[2,2],[3,3]]

输出: 4

说明: 初始化二维数组M = [[0, 0, 0],[0, 0, 0],[0, 0, 0]]，然后取ops中的第一个数组[2,2]，也就是0<=i<2,0<=j<2，所以M[0][0]，M[0][1]，M[1][0]，M[1][1]都自加1，此时M=[[1, 1, 0],[1, 1, 0]，[0, 0, 0]]。然后取ops中的第二个数组[3,3]，表明0<=i<3,0<=j<3，分别对M中的元素加1，此次操作是对数组中所有元素都加1，因为M的下标最大到2，此时M = [[2, 2, 1],[2, 2, 1],[1, 1, 1]]，其中2是最大值，出现了4次，所以返回4。

注意：

m和n的范围是[1,40000]。
a的范围是[1，m]，b的范围是[1，n]。
ops的范围不超过10,000。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 解题

通过观察上面的例子，我们可以知道，被加的次数最多的元素值最大，其次数就是坐标范围之积，就是题目要求的M中值最大的元素的个数。例题中，被加次数最多坐标范围是[2,2]，这中间有4个数。我们只需要找到每次操作的坐标最小值，就可以锁定操作的最小范围，此范围内的值最大，因为每次都会把该范围内的数加1。题目已经告诉了M的行是m，列是n，而每次操作的坐标的ops中数组的前两位元素，取两者之间的最小行值、列值，最后相乘就是最大值的个数。特殊情况就是，给的ops为null或者是个空数组，那么值最大的元素值为0，次数就是M的行列之积。

public int maxCount(int m, int n, int[][] ops) {
    if (ops == null || ops.length == 0) {
        return m*n;
    }
    for (int[] temp : ops) {
        m = Math.min(m, temp[0]);
        n = Math.min(n, temp[1]);
    }
    return m*n;
}