LeetCode-day17-2713. 矩阵中严格递增的单元格数

LeetCode-day17-2713. 矩阵中严格递增的单元格数

  • 题目描述
  • 示例
    • 示例1:
    • 示例2:
    • 示例3:
  • 思路
  • 代码

题目描述

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat,你可以选择任一单元格作为 起始单元格

从起始单元格出发,你可以移动到 同一行或同一列 中的任何其他单元格,但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程,从一个单元格移动到另一个单元格,直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量

返回一个表示可访问单元格最大数量的整数。

示例

示例1:

在这里插入图片描述

输入:mat = [[3,1],[3,4]]
输出:2
解释:上图展示了从第 1 行、第 2 列的单元格开始,可以访问 2 个单元格。可以证明,无论从哪个单元格开始,最多只能访问 2 个单元格,因此答案是 2 。

示例2:

在这里插入图片描述

输入:mat = [[1,1],[1,1]]
输出:1
解释:由于目标单元格必须严格大于当前单元格,在本示例中只能访问 1 个单元格。

示例3:

在这里插入图片描述

输入:mat = [[3,1,6],[-9,5,7]]
输出:4
解释:上图展示了从第 2 行、第 1 列的单元格开始,可以访问 4 个单元格。可以证明,无论从哪个单元格开始,最多只能访问 4 个单元格,因此答案是 4 。

思路

动态规划。此题为难题~

代码

public int maxIncreasingCells(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        TreeMap<Integer, List<int[]>> g = new TreeMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                g.computeIfAbsent(mat[i][j],k -> new ArrayList<>()).add(new int[]{i,j});
            }
        }

        int ans =0;
        int[] row = new int[m];
        int[] col = new int[n];
        for (List<int[]> pos : g.values()) {
            int[] f = new int[pos.size()];
            for (int k = 0; k < pos.size(); k++) {
                int[] p = pos.get(k);
                int i = p[0];
                int j = p[1];
                f[k] = Math.max(row[i],col[j])+1;
                ans = Math.max(ans,f[k]);
            }
            for (int k = 0; k < pos.size(); k++) {
                int[] p = pos.get(k);
                int i = p[0];
                int j = p[1];
                row[i] = Math.max(row[i],f[k]);
                col[j] = Math.max(col[j],f[k]);
            }
        }
        return ans;
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/724551.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

D111FCE01LC2NB70带流量调节派克比例阀

D111FCE01LC2NB70带流量调节派克比例阀 派克比例阀&#xff1a;由于采用&#xff08;秉圣135陈工6653询3053&#xff09;电液混合控制技术&#xff0c;响应速度更快、精度更高、控制更平稳。同时&#xff0c;由于采用高质量的材料制造&#xff0c;具有较高的承压能力和抗磨损性…

示例:推荐一个应用Adorner做的消息对话框

一、目的&#xff1a;开发过程中&#xff0c;经常用到对话框&#xff0c;下面演示一个应用Adorner做的带遮盖层蒙版的控件&#xff0c;使用MainWindow的Adorner实现不需要额外定义遮盖层&#xff0c;使用Object作为参数&#xff0c;可自定义DataTemplate定制消息显示样式 二、效…

react使用OpenLayers实现类似船某网在地图放大时展示具体船舶符号缩小时显示聚合小点效果

一、效果 如图所示&#xff0c;地图缩小&#xff08;即比例尺放大&#xff09;时&#xff0c;显示聚合小绿点&#xff1b; 地图放大&#xff08;比例尺缩小&#xff09;时&#xff0c;展示具体船舶符号&#xff1a; 二、思路 1&#xff09;设置2个图层&#xff0c;一个展示…

尚品汇项目2

p68 加入产品个数操作 p69 加入购物车

GitHub爆赞!最适合新手入门的教程——笨方法学Python 3

“Python 是一门既容易上手又强大的编程语言。”这句话本身并无大碍&#xff0c;但需要注意的是&#xff0c;正因为它既好学又好用&#xff0c;所以很多 Python 程序员只用到了其强大功能的一小部分。 今天给小伙伴们分享的这份手册以习题的方式引导读者一步一步学习编程&…

【最有效】解决anaconda的虚拟环境重复目录问题

安装某些原因导致虚拟环境出现重复的问题&#xff0c;有的博客介绍删除“C:\Users\Success\.conda”中的environments.txt&#xff0c;但是自己尝试了对本计算机不管用&#xff0c;甚至把整个.conda文件删除问题依旧。 现在介绍一下最简单管用的办法&#xff1a; 打开“C:\Us…

鸿蒙HarmonyOS实战:状态管理和传值

状态管理 State State是一个装饰器&#xff0c;是用来存放数据的&#xff0c;比较好理解 由State的数据来进行状态驱动视图更新 代码很简单 State count: number 0; 需要注意的是State初始化的数据必须赋值 这里我们讨论简单用法&#xff0c;至于复杂的用法可以到项目中介绍…

Certificate数字证书的有效性验证

1.证书相关概念 在讲证书有效性验证的逻辑之前&#xff0c;先了解几个概念。 证书颁发机构&#xff1a;一般为运营数字证书的机构&#xff0c;该机构负责证书的签发、吊销等生命周期管理。证书链&#xff1a;证书颁发机构一般会由多个组成&#xff0c;为树状层级&#xff0c;第…

嵌入式开发十八:USART串口通信实验

上一节我们学习了串口通信的基本理论&#xff0c;串口通信是学习单片机的一个重要的一步&#xff0c;非常重要&#xff0c;这一节我们通过实验来学习串口通信的使用&#xff0c;以及串口的接收中断的使用。 一、发送单个字节uint8_t数据或者字符型数据 实现的功能&#xff1a;…

conda下安装32位版本python

前言&#xff1a;当前主流的系统为64bit系统&#xff0c;conda软件为64bit软件&#xff0c;因此使用conda创建虚拟环境安装python时默认安装的python为64bit版本&#xff0c;但部分研发场景需要调用32bit依赖&#xff0c;只能使用32bit的python&#xff0c;因此需要安装32bit的…

KVB投资安全小知识:如何识别一个货币是避险货币还是风险货币?

摘要 在全球经济不断变化的今天&#xff0c;理解货币的避险属性和风险特征对投资者至关重要。本文将详细探讨如何准确识别一个货币是避险货币还是风险货币&#xff0c;并结合具体的货币案例分析它们的本质差异。通过深入分析不同因素对货币走势的影响&#xff0c;帮助读者在金…

【面试八股总结】Redis数据结构及底层实现

一、五种基本数据结构 Redis 提供了丰富的数据类型&#xff0c;常见的有五种数据类型&#xff1a;String&#xff08;字符串&#xff09;&#xff0c;Hash&#xff08;哈希&#xff09;&#xff0c;List&#xff08;列表&#xff09;&#xff0c;Set&#xff08;集合&#xff0…

【Java】已解决java.util.EmptyStackException异常

文章目录 一、问题背景二、可能出错的原因三、错误代码示例四、正确代码示例五、注意事项 已解决java.util.EmptyStackException异常 一、问题背景 java.util.EmptyStackException是Java在使用java.util.Stack类时可能会遇到的一个异常。这个异常通常在尝试从空的栈中弹出&am…

[吃瓜教程]概览西瓜书+南瓜书第1、2章

第一章 绪论 1.1机器学习的定义,什么是机器学习&#xff1f; 1&#xff09;机器学习是这样一门学科&#xff0c;它致力于研究如何通过计算的手段&#xff0c;利用经验来改善系统自身的性能。 2&#xff09;机器学习所研究的主要内容是关于在计算机上从数据中产生模型的算法&a…

【golang学习之旅】Go程序快速开始 Go程序开发的基本注意事项

系列文章 【golang学习之旅】使用VScode安装配置Go开发环境 【golang学习之旅】报错&#xff1a;a declared but not used 【golang学习之旅】Go 的基本数据类型 【golang学习之旅】深入理解字符串string数据类型 【golang学习之旅】go mod tidy 【golang学习之旅】记录一次 p…

linux配置Vnc Server给Windows连接

1. linux 安装必要vnc server和桌面组件 sudo apt -y install tightvncserversudo apt install xfce4 xfce4-goodies2. linux 配置vncserver密码 #bash vncserver参考: https://cn.linux-console.net/?p21846#google_vignette 3. 将启动桌面命令写入.vnc/xstartup # .vnc/x…

了解指标体系1:指标是大数据开发中的关键要素

在大数据开发的过程中&#xff0c;指标体系是一个至关重要的概念。本文将介绍什么是指标&#xff0c;为什么它们如此重要&#xff0c;以及如何在大数据项目中有效地构建和应用指标体系。 目录 什么是指标&#xff1f;指标的类型为什么指标如此重要&#xff1f;如何构建有效的指…

2024最新自动化测试 —— Jest 测试框架应用

什么是自动化测试 在软件测试中&#xff0c;自动化测试指的是使用独立于待测软件的其他软件来自动执行测试、比较实际结果与预期并生成测试报告这一过程。在测试流程已经确定后&#xff0c;测试自动化可以自动执行的一些重复但必要的测试工作。也可以完成手动测试几乎不可能完…

xcode和iPhone真机或者watch真机连接问题

1.如果真机是第一次连接xocde&#xff0c;就需要开启真机上的开发者模式&#xff0c;开启开发者模式的方式&#xff1a; iphone/ipad开启方式: 设置 > 隐私与安全 > 开发者模式 > 开启&#xff0c;然后重启就可以了 watch设置&#xff1a;很麻烦&#xff0c;看文章…