当前位置: 首页 > news >正文

求职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年字节二面的题目&#xff0c;我感觉这道题跟接雨水有点类似&#xff0c;最重要的思路还是要找到什么时候能形成矩形的这么个情况&#xff0c;某个范围的矩形的高度&#xff0c;是由最短的柱形来决定的。 我们先整理一下&#xff0c;解决这道…...

深入探索 Postman:使用 API 性能测试优化你的 Web 服务

引言 在当今快速发展的互联网时代&#xff0c;Web 服务的性能至关重要。API 作为服务之间的桥梁&#xff0c;其性能直接影响到整个应用的响应速度和用户体验。Postman&#xff0c;作为一个多功能的 API 开发工具&#xff0c;提供了强大的性能测试功能&#xff0c;帮助开发者评…...

校车购票小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;学生管理&#xff0c;我的乘车信息管理&#xff0c;车辆信息管理&#xff0c;座位管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;车辆信息&#xff0c;我的 开发系统…...

拯救数据危机!2024年最受欢迎的数据恢复软件评测

现在大家快速传输资料的方式都变成了电子档&#xff0c;有些数据是存储在电脑上&#xff0c;有些存储在手机&#xff0c;有的存储在U盘甚至其他一些电子设备上。电子设备存储数据方便&#xff0c;丢失数据也总在意料之外。很多时候我们多学会一个工具&#xff0c;比如转转大师数…...

记一次因为在html两个地方引入vue.js导致组件注入失败的问题

这个问题我遇到两次了&#xff0c;是在恼火&#xff0c;不对&#xff0c;三次了&#xff0c;我如果不做这个笔记&#xff0c;我确定我还会遇到第三次。 尾部这个去掉就行 因为头部有了 遇到这种bu g好恼火&#xff0c;解决了又怎么样呢&#xff1f;重蹈覆辙的滋味不好受...

Postman中的智慧重试:API测试用例的错误处理与重试逻辑设置

Postman中的智慧重试&#xff1a;API测试用例的错误处理与重试逻辑设置 在API测试过程中&#xff0c;错误处理和重试逻辑是确保测试准确性和可靠性的重要环节。Postman提供了多种功能来处理测试中可能出现的错误&#xff0c;并允许自定义重试逻辑以适应不同的测试场景。本文将…...

docker部署本地词向量模型

开源项目&#xff1a;GitHub - huggingface/text-embeddings-inference: A blazing fast inference solution for text embeddings models 1. 下载词向量模型 参考我的另一篇博客&#xff1a;langchain 加载本地词向量模型 2. 部署词向量模型 就三行命令 model/data/BAAI/…...

接口自动化中对于文件上传的处理方法

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

Java高频面试题分享

文章目录 1. 策略模式怎么控制策略的选取1.1 追问&#xff1a;如果有100种策略呢&#xff1f;1.2 追问&#xff1a;什么情况下初始化Map 2. 什么是索引&#xff1f;什么时候用索引&#xff1f;2.1 追问&#xff1a;怎么判断系统什么时候用量比较少2.2 追问&#xff1a;如何实时…...

kvm虚拟化平台部署

kvm虚拟化平台部署 kvm概念简介 kvm自linux2.6版本以后就整合到内核中&#xff0c;因此可以看做是一个原生架构. kvm虚拟化架构 硬件底层提供物理层面的硬件支持 linux&#xff08;host&#xff09;&#xff0c;就相当于这个架构中的宿主机&#xff0c;上面运行了多个虚拟机。…...

利用arthas热更新class文件

利用arthas热更新class文件 背景&#xff1a;发现一个bug&#xff0c;家里难以复现&#xff0c;需要在现场环境更新几行代码验证。 arthas-boot version: 3.7.1 java -jar arthas-boot.jar启动arthas 1、利用arthas的sc命令查找确定类名称 sc com.**2、反编译为java文件 …...

天机学堂 第四天 高并发优化总结

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

Canva收购Leonardo.ai,增强生成式AI技术能力

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

前端练习<HtmlCSS>——照片墙(附完整代码及实现效果)

这个小练习也来源于b站up小K师兄&#xff0c;大家可以通过下面的链接学习哦~up讲的非常详细。 纯CSS写一个简单酷炫的照片墙效果&#xff5e; 先看一下这个照片墙的效果&#xff1a; 1.鼠标没有放到图片上时&#xff0c;照片同比例&#xff0c;每张照片都有倒影的效果。 2.然…...

PHP基于微信小程序的打车平台-计算机毕业设计源码78689

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

Vue element ui分页组件示例

https://andi.cn/page/621615.html...

redis存储结构

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

SQL Server 数据误删的恢复

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

墨烯的C语言技术栈-C语言基础-018

char c; //1byte字节 8bit比特位 int main() { int a 10; //向内存申请四个字节,存储10 &a; //取地址操作符 return 0; } 每个字节都有地址 而a的地址就是它第一个字节的地址 要先开始调试才可以查看监控和查看内存 左边是地址 中间是内存中的数据 最后面的是…...

C端与B端 - 第一弹 - 理解和区分C端与B端软件开发

作者&#xff1a;逍遥Sean 简介&#xff1a;一个主修Java的Web网站\游戏服务器后端开发者 主页&#xff1a;https://blog.csdn.net/Ureliable 觉得博主文章不错的话&#xff0c;可以三连支持一下~ 如有疑问和建议&#xff0c;请私信或评论留言&#xff01; 前言 在软件开发领域…...

Claude学术写作辅助应用:3天写出SCI初稿?实测7个被顶刊编辑默许的Prompt技巧

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Claude学术写作辅助应用&#xff1a;3天写出SCI初稿&#xff1f;实测7个被顶刊编辑默许的Prompt技巧 为什么Claude比GPT更适配学术写作场景 Claude系列模型&#xff08;尤其是Claude 3.5 Sonnet&#…...

如何重塑贴吧体验:贴吧Lite带来的极致纯净浏览革新

如何重塑贴吧体验&#xff1a;贴吧Lite带来的极致纯净浏览革新 【免费下载链接】TiebaLite 贴吧 Lite 项目地址: https://gitcode.com/gh_mirrors/tieb/TiebaLite 厌倦了官方贴吧应用的臃肿体验和无处不在的广告干扰&#xff1f;贴吧Lite作为一款革命性的第三方贴吧客户…...

DiskSpd深度解析:企业级存储性能调优的架构视角与实战指南

DiskSpd深度解析&#xff1a;企业级存储性能调优的架构视角与实战指南 【免费下载链接】diskspd DISKSPD is a storage load generator / performance test tool from the Windows/Windows Server and Cloud Server Infrastructure Engineering teams 项目地址: https://gitc…...

如何用Playnite打造你的终极游戏库:统一管理Steam、Epic、GOG等20+平台游戏

如何用Playnite打造你的终极游戏库&#xff1a;统一管理Steam、Epic、GOG等20平台游戏 【免费下载链接】Playnite Video game library manager with support for wide range of 3rd party libraries and game emulation support, providing one unified interface for your gam…...

市面上有哪些是真正性价比高的降AIGC软件(轻松压低AI生成疑似率)

最崩溃的不是查重难题&#xff0c;而是查重达标却AI率超标亮红灯&#xff01;很多工具只会简单同义词替换、浅层改字&#xff0c;根本洗不掉AI专属句式、行文逻辑和高频模板话术&#xff0c;学校AIGC检测一查一个准&#xff0c;论文直接翻车。 本篇结合全网实测数据&#xff0c…...

让你的电脑拥有AI大脑:UI-TARS桌面助手实战指南

让你的电脑拥有AI大脑&#xff1a;UI-TARS桌面助手实战指南 【免费下载链接】UI-TARS-desktop The Open-Source Multimodal AI Agent Stack: Connecting Cutting-Edge AI Models and Agent Infra 项目地址: https://gitcode.com/GitHub_Trending/ui/UI-TARS-desktop 你是…...

PPT怎么转PDF?一键快捷操作与全方位转换方法测评

在日常工作中&#xff0c;我们经常需要将PowerPoint演示文稿转换成PDF格式。无论是为了保证演示文件的兼容性、方便分享给他人&#xff0c;还是用于打印和存档&#xff0c;PPT转PDF都是一项必不可少的技能。本文将为你深入讲解PPT转PDF的多种方法&#xff0c;包括快捷键操作、软…...

【2026年华为暑期实习-非AI方向(通软嵌软测试算法数据科学)- 5月22日-第三题- 数据传输网络调优】(题目+思路+JavaC++Python解析+在线测试)

题目内容 有一个由 NNN 个数据交换节点(编号为 000 到 N−1N-1...

Yarn Spinner终极指南:10分钟学会编写专业游戏交互对话

Yarn Spinner终极指南&#xff1a;10分钟学会编写专业游戏交互对话 【免费下载链接】YarnSpinner The core compiler and engine-agnostic components for Yarn Spinner, the friendly dialogue tool. 项目地址: https://gitcode.com/gh_mirrors/ya/YarnSpinner Yarn Sp…...

5个步骤掌握ScriptHookV:GTA V脚本开发终极指南

5个步骤掌握ScriptHookV&#xff1a;GTA V脚本开发终极指南 【免费下载链接】ScriptHookV An open source hook into GTAV for loading offline mods 项目地址: https://gitcode.com/gh_mirrors/sc/ScriptHookV 你是否曾梦想过为GTA V创造属于自己的游戏模组&#xff1f…...