Сложность: Easy
Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi.
Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций.
Пример:
Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.
👨💻 Алгоритм:
1⃣Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j).
2⃣Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])).
3⃣Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y.
😎 Решение:
class Solution {
function maxCount($m, $n, $ops) {
$minA = $m;
$minB = $n;
foreach ($ops as $op) {
$minA = min($minA, $op[0]);
$minB = min($minB, $op[1]);
}
return $minA * $minB;
}
}Ставь 👍 и забирай 📚 Базу знаний