{"id":2255,"date":"2018-03-20T21:04:47","date_gmt":"2018-03-21T04:04:47","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2255"},"modified":"2018-03-20T21:04:59","modified_gmt":"2018-03-21T04:04:59","slug":"leetcode-598-range-addition-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-598-range-addition-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 598. Range Addition II"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

https:\/\/leetcode.com\/problems\/range-addition-ii\/description\/<\/a><\/p>\n

Given an m * n matrix\u00a0M<\/b>\u00a0initialized with all\u00a00<\/b>‘s and several update operations.<\/p>\n

Operations are represented by a 2D array, and each operation is represented by an array with two\u00a0positive<\/b>integers\u00a0a<\/b>\u00a0and\u00a0b<\/b>, which means\u00a0M[i][j]<\/b>\u00a0should be\u00a0added by one<\/b>\u00a0for all\u00a00 <= i < a<\/b>\u00a0and\u00a00 <= j < b<\/b>.<\/p>\n

You need to count and return the number of maximum integers in the matrix after performing all the operations.<\/p>\n

Example 1:<\/b><\/p>\n

Input:<\/b> \r\nm = 3, n = 3\r\noperations = [[2,2],[3,3]]\r\nOutput:<\/b> 4\r\nExplanation:<\/b> \r\nInitially, M = \r\n[[0, 0, 0],\r\n [0, 0, 0],\r\n [0, 0, 0]]\r\n\r\nAfter performing [2,2], M = \r\n[[1, 1, 0],\r\n [1, 1, 0],\r\n [0, 0, 0]]\r\n\r\nAfter performing [3,3], M = \r\n[[2, 2, 1],\r\n [2, 2, 1],\r\n [1, 1, 1]]\r\n\r\nSo the maximum integer in M is 2, and there are four of it in M. So return 4.\r\n<\/pre>\n
Note:<\/b><\/p>\n
    \n
  1. The range of m and n is [1,40000].<\/li>\n
  2. The range of a is [1,m], and the range of b is [1,n].<\/li>\n
  3. The range of operations size won’t exceed 10,000.<\/li>\n<\/ol>\n
    Solution:<\/h1>\n
    Time Complexity: O(n)<\/p>\n
    Space Complexity: O(1)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 9 ms\r\nclass Solution {\r\npublic:\r\n  int maxCount(int m, int n, vector<vector<int>>& ops) {\r\n    for (const auto& range : ops) {\r\n      m = min(m, range[0]);\r\n      n = min(n, range[1]);\r\n    }\r\n    return m * n;\r\n  }\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem https:\/\/leetcode.com\/problems\/range-addition-ii\/description\/ Given an m * n matrix\u00a0M\u00a0initialized with all\u00a00‘s and several update operations. Operations are represented by a 2D array, and each operation is…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[222,216,139],"class_list":["post-2255","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-easy","tag-matrix","tag-range","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2255","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2255"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2255\/revisions"}],"predecessor-version":[{"id":2257,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2255\/revisions\/2257"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2255"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2255"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2255"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}