598.范围求和-ii.md

598.范围求和-ii

/*
 * @lc app=leetcode.cn id=598 lang=typescript
 *
 * [598] 范围求和 II
 */

// @lc code=start
function maxCount(m: number, n: number, ops: number[][]): number {}
// @lc code=end

解法 1: 贪心

• 时间复杂度:
• 空间复杂度:

假设第一次操作为 [a,b],第二次为 [a1,b1],则两次操作之后的最大区域为 0,0 ~ a,b 和 0,0 ~ a1,b1 重叠的地方,既 0,0 ~ min(a,a1),min(b,b1) 可以推导出 n 次操作后的最大区域为 0,0 ~ min(a,a1..an),min(b,b1..bn),遍历操作数组,每次记录最小的 a 和 b 即可

function maxCount(m: number, n: number, ops: number[][]): number {
  let [x, y] = [m, n]
  for (const [a, b] of ops) {
    x = Math.min(x, a)
    y = Math.min(y, b)
  }
  return x * y
}

Case

test.each([
  {
    input: {
      m: 3,
      n: 3,
      operations: [
        [2, 2],
        [3, 3],
      ],
    },
    output: 4,
  },
])('input: m = $input.m, n = $input.n, operations = $input.operations', ({ input: { m, n, operations }, output }) => {
  expect(maxCount(m, n, operations)).toEqual(output)
})