求职Leetcode题目(2)
1.柱状图中最大的矩形
据说这是2024年字节二面的题目,我感觉这道题跟接雨水有点类似,最重要的思路还是要找到什么时候能形成矩形的这么个情况,某个范围的矩形的高度,是由最短的柱形来决定的。
我们先整理一下,解决这道题,我们要知道高和宽,高好解决,至于这个宽,我们要注意宽的长度是取决于范围内最矮高度的柱子
这道题首先我们想到的思路是用栈,因为我们每次往后遍历元素的时候,我们需要找到一个元素比上一个小的元素,找到了之后,我们从这个元素开始一个一个向里扩张,计算每次的宽和高,这就需要我们每次用完一个元素然后抛掉,这符合先进后出的思想,所以这就是我们用栈的原因。
- 基本思路是枚举每一个高度的左右边界,所以我们定义:
- left数组:表示高度为heights[i]的左边界
- right数组:表示高度为heights[i]的右边届
- 左右边界都是高度满足:大于等于heights[i]的下一个位置,所以我们计算的时候是heights[i] * (right[i] - left[i]-1)
- 默认高度为heights[i]的右边届为len;
- 遍历数组中的元素,在栈中始终存储升序排序的比heights[i]小的下标
- 所以如果栈不为空且高度大于heights[i],我们让它出栈,并且赋予右边届为i,直到一个小于heights[i]的栈中元素或者栈为空
- 如果栈长度为0,那么说明没有比它小的,所以左边界为-1,否则左边届为栈顶的元素
- 遍历高度为heights[i]的左右边界进行计算,找出最大值即可。
public class CallerTask{public static int largestRectangleArea(int[] heights) {// 初始化最终结果为0int res = 0;int n =heights.length;Stack<Integer> stack = new Stack<>();int[] newHeights = new int[n + 2];newHeights[0] = 0;newHeights[newHeights.length-1] = 0;for (int i = 1; i < heights.length + 1; i++) {newHeights[i] = heights[i - 1];}// 开始遍历for (int i = 0; i < newHeights.length; i++) {// 如果栈不为空且当前考察的元素值小于栈顶元素值,// 则表示以栈顶元素值为高的矩形面积可以确定while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {// 弹出栈顶元素int cur = stack.pop();// 获取栈顶元素对应的高int curHeight = newHeights[cur];// 栈顶元素弹出后,新的栈顶元素就是其左侧边界int leftIndex = stack.peek();// 右侧边界是当前考察的索引int rightIndex = i;// 计算矩形宽度int curWidth = rightIndex - leftIndex - 1;// 计算面积res = Math.max(res, curWidth * curHeight);}// 当前考察索引入栈stack.push(i);}return res;}
}
2.最大矩形
如果我们把矩阵看作:以第三行为底边,每一列从下往上连续的1的个数作为高度的柱状图,如图所示:
- 问题就转化成了柱状图中最大的矩形
- 直接套用那一题的解法,就可以以O(n)的复杂度算出该柱状图中最大的矩形的面积是 6
- 但是这例子中只是特别选取了第3行作为底边,事实上选择哪一行作为底边是不确定的。
- 因此这道题我们需要对矩阵中以每一行作为底边的柱状图都求解一次最大矩形面积,再取最大值作为答案即可。
class Solution {public int maximalRectangle(char[][] matrix) {if (matrix.length == 0 || matrix[0].length == 0) {return 0;}int m = matrix.length;int n = matrix[0].length;int res = 0;// 柱状图高度数组。 前后增加一个高度为0的 “哨兵”,避免判断栈空,简化代码int[] heights = new int[n + 2];// 对每i行及以上看成柱状图,求一次“柱状图中的最大矩形”for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) { // 每一列的高度,要么为0,要么是上一行该列高度 + 1heights[j + 1] = matrix[i][j] == '0' ? 0 : 1 + heights[j + 1];}// 单调栈法求解 “柱状图最大矩形”Deque<Integer> stack = new ArrayDeque<>(m);stack.addLast(0);for (int j = 1; j < heights.length; j++) {while (heights[j] < heights[stack.peekLast()]) {int h = heights[stack.pollLast()];int w = j - stack.peekLast() - 1;res = Math.max(res, h * w);}stack.addLast(j);}}return res;}
}
3.括号生成
通过观察我们可以发现,生成的任何括号组合中都有两个规律:
1,括号组合中左括号的数量等于右括号的数量
2,括号组合中任何位置左括号的数量都是大于等于右括号的数量
第一条很容易理解,我们来看第二条,比如有效括号"(())()",在任何一个位置右括号的数量都不大于左括号的数量,所以他是有效的。如果像这样"())()"第3个位置的是右括号,那么他前面只有一个左括号,而他和他前面的右括号有2个,所以无论如何都不能组合成有效的括号。搞懂了上面的原理,我们就以n等于2为例来画个图看一下。
public List<String> generateParenthesis(int n) {List<String> res = new ArrayList<>();dfs(res, n, n, "");return res;}private void dfs(List<String> res, int left, int right, String curStr) {if (left == 0 && right == 0) { // 左右括号都不剩余了,说明找到了有效的括号res.add(curStr);return;}//左括号只有剩余的时候才可以选,如果左括号的数量已经选完了,是不能再选左括号了。//如果选完了左括号我们是还可以选择右括号的。if (left < 0)return;// 如果右括号剩余数量小于左括号剩余的数量,说明之前选择的无效if (right < left)return;//选择左括号dfs(res, left - 1, right, curStr + "(");//选择右括号dfs(res, left, right - 1, curStr + ")");}
相关文章:

求职Leetcode题目(2)
1.柱状图中最大的矩形 据说这是2024年字节二面的题目,我感觉这道题跟接雨水有点类似,最重要的思路还是要找到什么时候能形成矩形的这么个情况,某个范围的矩形的高度,是由最短的柱形来决定的。 我们先整理一下,解决这道…...
深入探索 Postman:使用 API 性能测试优化你的 Web 服务
引言 在当今快速发展的互联网时代,Web 服务的性能至关重要。API 作为服务之间的桥梁,其性能直接影响到整个应用的响应速度和用户体验。Postman,作为一个多功能的 API 开发工具,提供了强大的性能测试功能,帮助开发者评…...

校车购票小程序的设计
管理员账户功能包括:系统首页,个人中心,学生管理,我的乘车信息管理,车辆信息管理,座位管理,系统管理 微信端账号功能包括:系统首页,车辆信息,我的 开发系统…...

拯救数据危机!2024年最受欢迎的数据恢复软件评测
现在大家快速传输资料的方式都变成了电子档,有些数据是存储在电脑上,有些存储在手机,有的存储在U盘甚至其他一些电子设备上。电子设备存储数据方便,丢失数据也总在意料之外。很多时候我们多学会一个工具,比如转转大师数…...

记一次因为在html两个地方引入vue.js导致组件注入失败的问题
这个问题我遇到两次了,是在恼火,不对,三次了,我如果不做这个笔记,我确定我还会遇到第三次。 尾部这个去掉就行 因为头部有了 遇到这种bu g好恼火,解决了又怎么样呢?重蹈覆辙的滋味不好受...
Postman中的智慧重试:API测试用例的错误处理与重试逻辑设置
Postman中的智慧重试:API测试用例的错误处理与重试逻辑设置 在API测试过程中,错误处理和重试逻辑是确保测试准确性和可靠性的重要环节。Postman提供了多种功能来处理测试中可能出现的错误,并允许自定义重试逻辑以适应不同的测试场景。本文将…...
docker部署本地词向量模型
开源项目:GitHub - huggingface/text-embeddings-inference: A blazing fast inference solution for text embeddings models 1. 下载词向量模型 参考我的另一篇博客:langchain 加载本地词向量模型 2. 部署词向量模型 就三行命令 model/data/BAAI/…...

接口自动化中对于文件上传的处理方法
正常的接口自动化基本都是json的格式,对于文件上传是一种特殊的格式是表单格式针对这种表单格式在接口自动化中怎么处理,主要通过工作中使用的一个实际的例子进行分享 举例:web上需要导入一个文件实现相关的功能,主要通过两个接口…...

Java高频面试题分享
文章目录 1. 策略模式怎么控制策略的选取1.1 追问:如果有100种策略呢?1.2 追问:什么情况下初始化Map 2. 什么是索引?什么时候用索引?2.1 追问:怎么判断系统什么时候用量比较少2.2 追问:如何实时…...

kvm虚拟化平台部署
kvm虚拟化平台部署 kvm概念简介 kvm自linux2.6版本以后就整合到内核中,因此可以看做是一个原生架构. kvm虚拟化架构 硬件底层提供物理层面的硬件支持 linux(host),就相当于这个架构中的宿主机,上面运行了多个虚拟机。…...
利用arthas热更新class文件
利用arthas热更新class文件 背景:发现一个bug,家里难以复现,需要在现场环境更新几行代码验证。 arthas-boot version: 3.7.1 java -jar arthas-boot.jar启动arthas 1、利用arthas的sc命令查找确定类名称 sc com.**2、反编译为java文件 …...

天机学堂 第四天 高并发优化总结
前端每隔15秒就发起一次请求,将播放记录写入数据库。 但问题是,提交播放记录的业务太复杂了,其中涉及到大量的数据库操作: 如何进行优化 单机并发能力 变同步为异步 合并写请求 提高单机并发:优化SQL,尽…...

Canva收购Leonardo.ai,增强生成式AI技术能力
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...

前端练习<HtmlCSS>——照片墙(附完整代码及实现效果)
这个小练习也来源于b站up小K师兄,大家可以通过下面的链接学习哦~up讲的非常详细。 纯CSS写一个简单酷炫的照片墙效果~ 先看一下这个照片墙的效果: 1.鼠标没有放到图片上时,照片同比例,每张照片都有倒影的效果。 2.然…...

PHP基于微信小程序的打车平台-计算机毕业设计源码78689
摘 要 本文介绍的是基于PHP开发的打车平台小程序。该系统旨在为用户提供一个便捷、高效的平台,以实现网约车的打车功能。随着社交媒体和互联网的普及,网约车已成为日常交通中常见的形式。然而,传统的打车方式存在不方便、不及时等问题。 微信…...

Vue element ui分页组件示例
https://andi.cn/page/621615.html...

redis存储结构
一、整体结构图 二、redisDb结构体 Redis是一个高性能的键值存储系统,它支持多种类型的数据结构,如字符串、列表、集合、散列等。Redis数据库由多个数据库组成,每个数据库用一个redisDb结构体来表示。 dict *dict; dict指向一个字典结构的指…...

SQL Server 数据误删的恢复
在日常的数据库管理中,数据的误删操作是难以避免的。为了确保数据的安全性和完整性,我们必须采取一些措施来进行数据的备份和恢复。本文将详细介绍如何在 SQL Server 中进行数据的备份和恢复操作,特别是在发生数据误删的情况下。假设我们已经…...

墨烯的C语言技术栈-C语言基础-018
char c; //1byte字节 8bit比特位 int main() { int a 10; //向内存申请四个字节,存储10 &a; //取地址操作符 return 0; } 每个字节都有地址 而a的地址就是它第一个字节的地址 要先开始调试才可以查看监控和查看内存 左边是地址 中间是内存中的数据 最后面的是…...
C端与B端 - 第一弹 - 理解和区分C端与B端软件开发
作者:逍遥Sean 简介:一个主修Java的Web网站\游戏服务器后端开发者 主页:https://blog.csdn.net/Ureliable 觉得博主文章不错的话,可以三连支持一下~ 如有疑问和建议,请私信或评论留言! 前言 在软件开发领域…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...

Linux入门课的思维导图
耗时两周,终于把慕课网上的Linux的基础入门课实操、总结完了! 第一次以Blog的形式做学习记录,过程很有意思,但也很耗时。 课程时长5h,涉及到很多专有名词,要去逐个查找,以前接触过的概念因为时…...

java 局域网 rtsp 取流 WebSocket 推送到前端显示 低延迟
众所周知 摄像头取流推流显示前端延迟大 传统方法是服务器取摄像头的rtsp流 然后客户端连服务器 中转多了,延迟一定不小。 假设相机没有专网 公网 1相机自带推流 直接推送到云服务器 然后客户端拉去 2相机只有rtsp ,边缘服务器拉流推送到云服务器 …...