当前位置: 首页 > 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; 前言 在软件开发领域…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

深度解析:etcd 在 Milvus 向量数据库中的关键作用

目录 &#x1f680; 深度解析&#xff1a;etcd 在 Milvus 向量数据库中的关键作用 &#x1f4a1; 什么是 etcd&#xff1f; &#x1f9e0; Milvus 架构简介 &#x1f4e6; etcd 在 Milvus 中的核心作用 &#x1f527; 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...