Leetcode598:区间加法 II

news/2025/2/3 23:37:26 标签: 算法, 数据结构, leetcode, python3

题目描述:

给你一个 m x n 的矩阵 M 和一个操作数组 op 。矩阵初始化时所有的单元格都为 0 。ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时, M[x][y] 应该加 1。

在 执行完所有操作后 ,计算并返回 矩阵中最大整数的个数 。

代码思路:

步骤 1:找出所有操作中 ai 和 bi 的最小值。
步骤 2:返回这个最小值矩形区域的大小。

观察操作规则:每次操作都是一个矩形区域的增量操作,ops[i] = [ai, bi] 表示一个 ai x bi 的矩形区域,所有该区域内的元素都会加 1。
最小值确定法:通过分析所有操作的 ai 和 bi 值,我们可以知道矩阵中最大的值一定是在 ops 数组中的 ai 和 bi 的最小值所定义的区域内。例如,矩阵的最大值将出现在被最多操作的区域。
计算最大区域:最大值的数量是矩阵中受到所有操作影响最多的区域的大小。我们只需要找到 ai 和 bi 中的最小值,并返回该区域的大小

代码实现:

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        if not ops:
            return m * n
        
        # 找到所有操作中 ai 和 bi 的最小值
        min_a = min(op[0] for op in ops)
        min_b = min(op[1] for op in ops)
        
        # 最小矩形区域的大小
        return min_a * min_b


 


http://www.niftyadmin.cn/n/5841118.html

相关文章

复制粘贴小工具——Ditto

在日常工作中&#xff0c;复制粘贴是常见的操作&#xff0c;但Windows系统自带的剪贴板功能较为有限&#xff0c;只能保存最近一次的复制记录&#xff0c;这对于需要频繁复制粘贴的用户来说不太方便。今天&#xff0c;我们介绍一款开源、免费且功能强大的剪贴板增强工具——Dit…

【最后203篇系列】004 -Smarklink

说明 这个用来替代nginx。 最初是希望用nginx进行故障检测和负载均衡&#xff0c;花了很多时间&#xff0c;大致的结论是&#xff1a;nginx可以实现&#xff0c;但是是在商业版里。非得要找替代肯定可以搞出来&#xff0c;但是太麻烦了&#xff08;即使是nginx本身的配置也很烦…

【Qt】常用的容器

Qt提供了多个基于模板的容器类&#xff0c;这些容器类可用于存储指定类型的数据项。例如常用的字符串列表类 QStringList 可用来操作一个 QList<QString>列表。 Qt的容器类比标准模板库(standard template library&#xff0c;STL)中的容器类更轻巧、使用更安全且更易于使…

【论文复现】基于Otsu方法的多阈值图像分割改进鲸鱼优化算法

目录 1.摘要2.鲸鱼优化算法WOA原理3.改进策略4.结果展示5.参考文献6.代码获取 1.摘要 本文提出了一种基于Otsu方法的多阈值图像分割改进鲸鱼优化算法&#xff08;RAV-WOA&#xff09;。RAV-WOA算法能够在分割灰度图像和彩色图像时&#xff0c;自动选择最优阈值&#xff0c;并确…

【TypeScript】基础:数据类型

文章目录 TypeScript一、简介二、类型声明三、数据类型anyunknownnervervoidobjecttupleenumType一些特殊情况 TypeScript 是JavaScript的超集&#xff0c;代码量比JavaScript复杂、繁多&#xff1b;但是结构更清晰 一、简介 为什么需要TypeScript&#xff1f; JavaScript的…

【大数据技术】教程01:搭建完全分布式高可用大数据集群(VMware+CentOS+FinalShell)

搭建完全分布式高可用大数据集群&#xff08;VMwareCentOSFinalShell&#xff09; 资源下载 VMware Workstation Pro 16CentOS-Stream-10-latest-x86_64-dvd1.isoFinalShell 4.5.12 注&#xff1a;请在阅读本篇文章前&#xff0c;将以上资源下载下来。 写在前面 本章主要介…

Elasticsearch 指南 [8.17] | Search APIs

Search API 返回与请求中定义的查询匹配的搜索结果。 http GET /my-index-000001/_search Request GET /<target>/_search GET /_search POST /<target>/_search POST /_search Prerequisites 如果启用了 Elasticsearch 安全功能&#xff0c;针对目标数据流…

【tiktok 国际版抖抖♬♬ __ac_signature算法】逆向分析

一开始的参数是没有X-Bogus和 __ac_signature的 先是加密请求参数得到乱码。最终得到X-Bogus 然后请求参数添加了X-Bogus之后再去生成__ac_signature __ac_signature的生成需要用到X-Bogus