12.14 算法练习
1. 每日温度
算法思路
1. 单调栈的作用:记录我们遍历过的元素,与当前的元素方便对比,本质是以空间换时间;
2. 比较当前元素与栈顶元素的大小,当当前元素大于栈顶元素时,持续弹出栈顶元素下标,记录结果,并将当前元素下标加入到栈中;
3. 当前元素小于栈顶元素时,直接将栈顶元素下标加入到栈中。
注意点
当当前元素大于栈顶元素时,要弹出栈顶元素,若接下来的栈顶元素依然小于当前元素,要继续弹出。
代码
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] result = new int[temperatures.length];Stack<Integer> sk = new Stack<>();sk.push(0);for(int i = 1; i<temperatures.length; i++){if(temperatures[i] <= temperatures[sk.peek()]){sk.push(i);}else{while(!sk.isEmpty() && temperatures[i] > temperatures[sk.peek()]){int index = sk.pop();result[index] = i - index;}sk.push(i);}}return result;}
}
2. 下一个更大元素 I
算法思路
1. 题目所述要在数组2中找到与数组1相同的元素,并将数组2中第一个比这个元素大的元素返回到数组1所对应的下标,说明值和索引之间需要一个映射关系,加之数组中没有重复元素,所以可以使用HashMap;
2. 判断数组2中当前元素与栈顶元素的大小,如果当前元素小于等于栈顶元素,则将当前元素下标放入栈内;
3. 若当前元素大于栈顶元素,则判断该栈顶元素是否在数组1中存在,若存在,则取数组1索引,加入结果集中,再弹出该栈顶元素;若不存在,则直接弹出;直到当前元素小于等于栈顶元素,再将当前元素加入栈中。
注意点
由于不存在,result返回-1,使用要将result数组初始化为全是-1的数组。
代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] result = new int[nums1.length];Arrays.fill(result, -1);Map<Integer, Integer> map = new HashMap<>();Stack<Integer> sk = new Stack<>();sk.push(0);for(int i = 0; i<nums1.length; i++){map.put(nums1[i], i);}for(int i = 0; i<nums2.length; i++){if(nums2[i] <= nums2[sk.peek()]){sk.push(i);}else{while(!sk.isEmpty() && nums2[i] > nums2[sk.peek()]){if(map.containsKey(nums2[sk.peek()])){result[map.get(nums2[sk.peek()])] = nums2[i];}sk.pop();} sk.push(i);}}return result;}
}
3. 下一个更大元素II
算法思路
可以通过拼接两个一模一样的数组,来模拟环形数组。
注意点
代码
class Solution {public int[] nextGreaterElements(int[] nums) {int[] result = new int[nums.length];Arrays.fill(result,-1);Stack<Integer> sk = new Stack<>();sk.push(0);for(int i = 1; i<2*nums.length; i++){int index = i % nums.length;if(nums[index] <= nums[sk.peek()]){sk.push(index);}else{while(!sk.isEmpty() && nums[index] > nums[sk.peek()]){result[sk.peek()] = nums[index];sk.pop();}sk.push(index);}}return result;}
}
4. 接雨水
算法思路
1. 做一个预处理:找出当前柱子左边比其高的柱子,和右边比其高的柱子,可以通过单调递增栈来实现;
2. 如果当前元素比栈顶元素大,那么栈顶元素右边第一个比它大的元素就是当前元素,栈顶元素右边的元素就是左边第一个比它大的元素;
3. 用单调栈来求解,实际是横向求解雨水体积。
注意点
1. 用 left、right、mid来表示柱子,思路清晰,不容易弄混。
代码
class Solution {public int trap(int[] height) {Stack<Integer> sk = new Stack<>();sk.push(0);int result = 0;for(int i = 1; i<height.length; i++){if(height[i] <= height[sk.peek()]){sk.push(i);}else{while(!sk.isEmpty() && height[i] > height[sk.peek()]){int mid = sk.pop();if(!sk.isEmpty()){int left = sk.peek();int h = Math.min(height[left], height[i]) - height[mid];int w = i - left -1;result += h*w;}}sk.push(i);}}return result;}
}
5. 柱状图中最大的矩形
算法思路
1. 以某个高度为基准向左右找比它矮的柱子,找到了就可以最多延伸到比它矮的那个位置,形成矩形;
2. 计算矩阵的宽,就是可以延伸的距离(比基准柱子矮的柱子不能延伸),right - left - 1,而矩阵的高是Height[i];
3. 和接雨水那道题最大的区别是,这个数组的首尾需要加0。
注意点
1. 在末尾的位置加一个0,避免本身数组是单调递增的,加入到栈内单调递减,从而触发不到计算过程的情况;
2. 在开头的位置加一个0,避免本身数组是单调递减的,加入到栈内单调递增,刚开始就进入计算过程,但是会出现左边没有值的情况,因为算法要比较三个柱子;
3. 很难,建议二刷。
代码
class Solution {public int largestRectangleArea(int[] heights) {Stack<Integer> sk = new Stack<>();sk.push(0);int [] newHeights = new int[heights.length + 2];newHeights[0] = 0;for(int i = 0; i<heights.length; i++){newHeights[i+1] = heights[i];}newHeights[newHeights.length-1] = 0;int result = 0;for(int i = 0; i<newHeights.length; i++){if(newHeights[i] >= newHeights[sk.peek()]){sk.push(i);}else{while(!sk.isEmpty() && newHeights[i] < newHeights[sk.peek()]){int mid = sk.pop();if(!sk.isEmpty()){int left = sk.peek();int w = i-left-1;result = Math.max(result, w * newHeights[mid]);}}sk.push(i);}}return result;}
}
相关文章:
12.14 算法练习
1. 每日温度 算法思路 1. 单调栈的作用:记录我们遍历过的元素,与当前的元素方便对比,本质是以空间换时间; 2. 比较当前元素与栈顶元素的大小,当当前元素大于栈顶元素时,持续弹出栈顶元素下标,…...
ASP.NET Core SignalR的分布式部署
假设聊天室程序被部署在两台服务器上,客户端1、2连接到了服务器A上的ChatRoomHub,客户端3、4连接到服务器B上的ChatRoomHub,那么客户端1发送群聊消息时,只有客户端1、2能够收到,客户端3、4收不到;在客户端3…...
Express 中间件
在构建 Web 应用程序时,中间件(Middleware)扮演着至关重要的角色。它允许你定义一系列的函数来处理 HTTP 请求和响应过程中的各种任务。Express.js 是 Node.js 上最流行的框架之一,以其简洁且强大的中间件机制著称。本文将深入探讨…...
ABB能源自动化选用宏集Cogent DataHub避免DCOM问题,实现高效、安全的数据传输
案例概况 ABB能源自动化公司通过宏集Cogent DataHub软件将电厂设施的数据实时传输到公司办公室,实现了OPC隧道/镜像解决方案,在电厂和公司网络之间建立了一个安全、可靠的连接,确保数据传输的高度安全,减少入侵风险。 ࿰…...
springboot239-springboot在线医疗问答平台(源码+论文+PPT+部署讲解等)
💕💕作者: 爱笑学姐 💕💕个人简介:十年Java,Python美女程序员一枚,精通计算机专业前后端各类框架。 💕💕各类成品Java毕设 。javaweb,ssm…...
【Elasticsearch】分析器的构成
在Elasticsearch中,分析器(Analyzer)是一个处理文本数据的管道,它将输入的文本转换为一系列词元(tokens),并可以对这些词元进行进一步的处理和规范化。分析器由以下三个主要组件构成:…...
Python 调用 Azure OpenAI API
在人工智能和机器学习快速发展的今天,Azure OpenAI 服务为开发者提供了强大的工具来集成先进的 AI 能力到他们的应用中。本文将指导您如何使用 Python 调用 Azure OpenAI API,特别是使用 GPT-4 模型进行对话生成。 准备工作 在开始之前,请确保您已经: 拥有一个 Azure 账户…...
数据结构 算法时间复杂度和空间复杂度
一、算法好坏的度量 【事前分析法】 算法设计好后,根据算法的设计原理,只要问题规模确定,算法中基本语句执⾏次数和需求资源个数 基本也就确定了。 ⽐如求1 2 3 ... n − 1 n ,可以设计三种算法: 算法Aÿ…...
CNN-BiGRU卷积神经网络双向门控循环单元多变量多步预测,光伏功率预测
CNN-BiGRU卷积神经网络双向门控循环单元多变量多步预测,光伏功率预测 代码下载:CNN-BiGRU卷积神经网络双向门控循环单元多变量多步预测,光伏功率预测 一、引言 1.1、研究背景及意义 随着全球能源危机和环境问题的日益严重,可再…...
钉钉位置偏移解决,钉钉虚拟定位打卡
虚拟定位打卡工具 一,介绍免费获取工具 一,介绍 提到上班打卡,职场人的内心戏估计能拍成一部连续剧。打卡,这俩字仿佛自带“紧箍咒”,让无数打工人又爱又恨。想象一下,你气喘吁吁地冲进办公室,…...
【面试集锦】如何设计SSO方案?和OAuth有什么区别?
如何设计SSO方案?和OAuth有什么区别?--楼兰 带你聊最纯粹的Java 如果面试问你,你会做一个权限系统吗?那你肯定会说做过。不就是各种登录、验证吗。我做的第一个CRUD应用就是注册、登录。简单!但是,如果问你在工作中真的做过权限系统吗?其实很多人都只能默默摇摇头。因…...
Python 基于 OpenCV 的人脸识别上课考勤系统(附源码,部署教程)
博主介绍:✌2013crazy、10年大厂程序员经历。全网粉丝12W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇&a…...
vcredist_x64.exe 是 Microsoft Visual C++ Redistributable 的 64 位版本
vcredist_x64.exe 是 Microsoft Visual C++ Redistributable 的 64 位版本,它提供了运行基于 Visual C++ 编写的应用程序所需的库文件。许多 Windows 应用程序都依赖这些库来正常运行,特别是使用 Visual Studio 编译的程序。 用途和重要性: 运行时库:vcredist_x64.exe 安装…...
Tailwind CSS 的核心理念
实用优先(Utility-First) Tailwind CSS 的最核心理念是"实用优先"。这种方法颠覆了传统的 CSS 开发方式,不再编写自定义的类名和样式规则,而是通过组合预定义的工具类来构建界面。这种方式带来了以下优势: …...
集成学习(二):从理论到实战(附代码)
接上一篇续写《集成学习(一):从理论到实战(附代码)》 五、实用算法 5.1 随机森林 随机森林在数据集的各个子样本上拟合许多决策树分类器,并使用平均来提高预测精度和控制过拟合。每一个分类器拟合了一部分随机样本,…...
HTML 链接
HTML 链接 引言 HTML(超文本标记语言)是构建网页的基础,而链接是网页中不可或缺的元素。链接不仅能够连接到其他网页,还能实现网页内部内容的跳转。本文将详细介绍HTML链接的用法、属性以及如何实现链接的优化。 HTML链接的基本…...
【机器学习】数据预处理之scikit-learn的Scaler与自定义Scaler类进行数据归一化
scikit-learn的Scaler数据归一化 一、摘要二、训练数据集和测试数据集的归一化处理原则三、scikit-learn中的Scalar类及示例四、自定义StandardScaler类进行数据归一化处理五、小结 一、摘要 本文主要介绍了scikit-learn中Scaler的使用方法,特别强调了数据归一化在…...
android的第一个app项目(java版)
一.学习java重要概念 java的基本类型的语言方法和C语言很像,这都是我们要学的东西和学过的东西。那些基础东西,就不和大家讨论了,一起看一下java的一些知识架构。 1.封装 封装是面向对象编程中的一个核心概念,它涉及到将数据和操…...
上位机知识篇---SSHSCP密钥与密钥对
文章目录 前言第一部分:SCP(Secure Copy Protocol)功能使用方法1.从本地复制到远程主机2.从远程主机复制到本地3.复制整个目录4.指定端口5.压缩传输 第二部分:SSH(Secure Shell)功能使用方法1.远程登录2.指…...
智慧物流新引擎:ARM架构工控机在自动化生产线中的应用
工业自动化程度的不断提升,对高性能、低功耗和高可靠性的计算设备需求日益增长。ARM架构工控机因其独特的优势,在多个工业领域得到了广泛应用。本文将深入探讨ARM架构工控机的特点及其在具体工业场景中的应用。 ARM架构工控机的主要优势 高效能与低功耗…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
