前往
大廳
主題

LeetCode - 598. Range Addition II 解題心得

Not In My Back Yard | 2020-12-03 00:00:01 | 巴幣 0 | 人氣 133

題目連結:


題目意譯:
給定你一個 m × n 的矩陣 M 其內容初始化為 0 以及一個操作序列 ops,其中 ops[i] = [ai, bi] 代表著對於所有滿足 0 <= x < ai and 0 <= y < bi 的 x 、 y 者,應將 M[x][y] 加 1 。

統計並回傳執行完所有操作後的矩陣中最大的整數之出現次數。

限制:
1 ≦ m 、 n ≦ 4 × 10 ^ 4
1 ≦ ops.length ≦ 10 ^ 4
ops[i].length == 2
1 ≦ ai ≦ m
1 ≦ bi ≦ n



範例測資:
範例 1:
輸入: m = 3 、 n = 3 、 ops = [[2,2],[3,3]]
輸出: 4
解釋: M 中最大的整數為 2 ,而其中有四個 2 在 M 之中。因此回傳 4 。

範例 2:
輸入: 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]]
輸出: 4

範例 3:
輸入: m = 3 、 n = 3 、 ops = []
輸出: 9


解題思維:
如果將每個給定的 ops[i] 視作一個矩形的其中一個頂點 (ai, bi),同時 (0, 0) 為該矩形的頂點 (ai, bi) 的對面之頂點。

因此,可以看到矩陣 M 中最大的數字出現的區域是由 ops 中所有矩形重疊而成的區域。

所以我們定義兩個變數 overlapX 以及 overlapY,一開始分別等於 m 以及 n。而對於每個 ops[i] 的 (ai, bi),我們按照以下式子更新這兩個變數:
overlapX = min(overlapX, ai)
overlapY = min(overlapY, bi)
ops 的所有操作看完之後,overlapX × overlapY 之值即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作