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

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. 单调栈的作用&#xff1a;记录我们遍历过的元素&#xff0c;与当前的元素方便对比&#xff0c;本质是以空间换时间&#xff1b; 2. 比较当前元素与栈顶元素的大小&#xff0c;当当前元素大于栈顶元素时&#xff0c;持续弹出栈顶元素下标&#xff0c;…...

ASP.NET Core SignalR的分布式部署

假设聊天室程序被部署在两台服务器上&#xff0c;客户端1、2连接到了服务器A上的ChatRoomHub&#xff0c;客户端3、4连接到服务器B上的ChatRoomHub&#xff0c;那么客户端1发送群聊消息时&#xff0c;只有客户端1、2能够收到&#xff0c;客户端3、4收不到&#xff1b;在客户端3…...

Express 中间件

在构建 Web 应用程序时&#xff0c;中间件&#xff08;Middleware&#xff09;扮演着至关重要的角色。它允许你定义一系列的函数来处理 HTTP 请求和响应过程中的各种任务。Express.js 是 Node.js 上最流行的框架之一&#xff0c;以其简洁且强大的中间件机制著称。本文将深入探讨…...

ABB能源自动化选用宏集Cogent DataHub避免DCOM问题,实现高效、安全的数据传输

案例概况 ABB能源自动化公司通过宏集Cogent DataHub软件将电厂设施的数据实时传输到公司办公室&#xff0c;实现了OPC隧道/镜像解决方案&#xff0c;在电厂和公司网络之间建立了一个安全、可靠的连接&#xff0c;确保数据传输的高度安全&#xff0c;减少入侵风险。 &#xff0…...

springboot239-springboot在线医疗问答平台(源码+论文+PPT+部署讲解等)

&#x1f495;&#x1f495;作者&#xff1a; 爱笑学姐 &#x1f495;&#x1f495;个人简介&#xff1a;十年Java&#xff0c;Python美女程序员一枚&#xff0c;精通计算机专业前后端各类框架。 &#x1f495;&#x1f495;各类成品Java毕设 。javaweb&#xff0c;ssm&#xf…...

【Elasticsearch】分析器的构成

在Elasticsearch中&#xff0c;分析器&#xff08;Analyzer&#xff09;是一个处理文本数据的管道&#xff0c;它将输入的文本转换为一系列词元&#xff08;tokens&#xff09;&#xff0c;并可以对这些词元进行进一步的处理和规范化。分析器由以下三个主要组件构成&#xff1a…...

Python 调用 Azure OpenAI API

在人工智能和机器学习快速发展的今天,Azure OpenAI 服务为开发者提供了强大的工具来集成先进的 AI 能力到他们的应用中。本文将指导您如何使用 Python 调用 Azure OpenAI API,特别是使用 GPT-4 模型进行对话生成。 准备工作 在开始之前,请确保您已经: 拥有一个 Azure 账户…...

数据结构 算法时间复杂度和空间复杂度

一、算法好坏的度量 【事前分析法】 算法设计好后&#xff0c;根据算法的设计原理&#xff0c;只要问题规模确定&#xff0c;算法中基本语句执⾏次数和需求资源个数 基本也就确定了。 ⽐如求1 2 3 ... n − 1 n &#xff0c;可以设计三种算法&#xff1a; 算法A&#xff…...

CNN-BiGRU卷积神经网络双向门控循环单元多变量多步预测,光伏功率预测

CNN-BiGRU卷积神经网络双向门控循环单元多变量多步预测&#xff0c;光伏功率预测 代码下载&#xff1a;CNN-BiGRU卷积神经网络双向门控循环单元多变量多步预测&#xff0c;光伏功率预测 一、引言 1.1、研究背景及意义 随着全球能源危机和环境问题的日益严重&#xff0c;可再…...

钉钉位置偏移解决,钉钉虚拟定位打卡

虚拟定位打卡工具 一&#xff0c;介绍免费获取工具 一&#xff0c;介绍 提到上班打卡&#xff0c;职场人的内心戏估计能拍成一部连续剧。打卡&#xff0c;这俩字仿佛自带“紧箍咒”&#xff0c;让无数打工人又爱又恨。想象一下&#xff0c;你气喘吁吁地冲进办公室&#xff0c;…...

【面试集锦】如何设计SSO方案?和OAuth有什么区别?

如何设计SSO方案?和OAuth有什么区别?--楼兰 带你聊最纯粹的Java ​ 如果面试问你,你会做一个权限系统吗?那你肯定会说做过。不就是各种登录、验证吗。我做的第一个CRUD应用就是注册、登录。简单!但是,如果问你在工作中真的做过权限系统吗?其实很多人都只能默默摇摇头。因…...

Python 基于 OpenCV 的人脸识别上课考勤系统(附源码,部署教程)

博主介绍&#xff1a;✌2013crazy、10年大厂程序员经历。全网粉丝12W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&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 的核心理念

实用优先&#xff08;Utility-First&#xff09; Tailwind CSS 的最核心理念是"实用优先"。这种方法颠覆了传统的 CSS 开发方式&#xff0c;不再编写自定义的类名和样式规则&#xff0c;而是通过组合预定义的工具类来构建界面。这种方式带来了以下优势&#xff1a; …...

集成学习(二):从理论到实战(附代码)

接上一篇续写《集成学习&#xff08;一&#xff09;&#xff1a;从理论到实战(附代码)》 五、实用算法 5.1 随机森林 随机森林在数据集的各个子样本上拟合许多决策树分类器&#xff0c;并使用平均来提高预测精度和控制过拟合。每一个分类器拟合了一部分随机样本&#xff0c;…...

HTML 链接

HTML 链接 引言 HTML&#xff08;超文本标记语言&#xff09;是构建网页的基础&#xff0c;而链接是网页中不可或缺的元素。链接不仅能够连接到其他网页&#xff0c;还能实现网页内部内容的跳转。本文将详细介绍HTML链接的用法、属性以及如何实现链接的优化。 HTML链接的基本…...

【机器学习】数据预处理之scikit-learn的Scaler与自定义Scaler类进行数据归一化

scikit-learn的Scaler数据归一化 一、摘要二、训练数据集和测试数据集的归一化处理原则三、scikit-learn中的Scalar类及示例四、自定义StandardScaler类进行数据归一化处理五、小结 一、摘要 本文主要介绍了scikit-learn中Scaler的使用方法&#xff0c;特别强调了数据归一化在…...

android的第一个app项目(java版)

一.学习java重要概念 java的基本类型的语言方法和C语言很像&#xff0c;这都是我们要学的东西和学过的东西。那些基础东西&#xff0c;就不和大家讨论了&#xff0c;一起看一下java的一些知识架构。 1.封装 封装是面向对象编程中的一个核心概念&#xff0c;它涉及到将数据和操…...

上位机知识篇---SSHSCP密钥与密钥对

文章目录 前言第一部分&#xff1a;SCP&#xff08;Secure Copy Protocol&#xff09;功能使用方法1.从本地复制到远程主机2.从远程主机复制到本地3.复制整个目录4.指定端口5.压缩传输 第二部分&#xff1a;SSH&#xff08;Secure Shell&#xff09;功能使用方法1.远程登录2.指…...

智慧物流新引擎:ARM架构工控机在自动化生产线中的应用

工业自动化程度的不断提升&#xff0c;对高性能、低功耗和高可靠性的计算设备需求日益增长。ARM架构工控机因其独特的优势&#xff0c;在多个工业领域得到了广泛应用。本文将深入探讨ARM架构工控机的特点及其在具体工业场景中的应用。 ARM架构工控机的主要优势 高效能与低功耗…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

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

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

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

JVM 内存结构 详解

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

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...