算法日记day 46(单调栈之下一个更大元素|柱状图中最大图形)

一、下一个更大元素1

题目:

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 j ,并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素,那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案,满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1:

输入:nums1 = [4,1,2], nums2 = [1,3,4,2].
输出:[-1,3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
- 4 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。
- 1 ,用加粗斜体标识,nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。

示例 2:

输入:nums1 = [2,4], nums2 = [1,2,3,4].
输出:[3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
- 2 ,用加粗斜体标识,nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ,用加粗斜体标识,nums2 = [1,2,3,4]。不存在下一个更大元素,所以答案是 -1 。

思路:

解法有许多种,这里采用单调栈和哈希表的解法,将数组nums1中的元素和索引全部存入哈希表中,遍历数组nums2,如果栈顶元素小于遍历到的元素,弹出该元素并与map比较有无相同元素,如果有则更新下标为对应的位置

代码:

public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 创建一个哈希表,用于存储 nums1 中每个元素及其索引HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++) {map.put(nums1[i], i);}// 创建结果数组,初始化为 -1int[] res = new int[nums1.length];Arrays.fill(res, -1);// 使用栈来跟踪 nums2 中的元素Stack<Integer> stack = new Stack<>();// 遍历 nums2for (int i = 0; i < nums2.length; i++) {// 当栈不为空且栈顶元素小于当前元素时while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {// 弹出栈顶元素,并更新结果数组int pre = nums2[stack.pop()];// 如果弹出的元素存在于 nums1 中if (map.containsKey(pre)) {res[map.get(pre)] = nums2[i];}}// 将当前元素的索引压入栈中stack.push(i);}return res;
}

这个哈希表用于存储 nums1 中每个元素及其对应的索引位置,以便快速查找。

遍历 nums1,将每个元素及其索引添加到哈希表中。

创建一个与 nums1 长度相同的结果数组 res,并用 -1 初始化,表示默认情况下每个元素的下一个更大元素是 -1

使用栈来存储 nums2 中的索引,以帮助跟踪当前元素和候选更大元素的比较。

如果栈不为空且栈顶元素小于当前元素,则弹出栈顶元素,检查它是否在 nums1 中。如果是,则更新结果数组中的对应位置。

将当前元素的索引压入栈中,以便后续元素可以用来比较。

暴力解法

public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 创建一个与 nums1 长度相同的结果数组 ans,初始值为 -1int[] ans = new int[nums1.length];for (int i = 0; i < ans.length; i++) {ans[i] = -1; // 默认情况下,所有结果初始化为 -1}// 遍历 nums1 中的每个元素for (int i = 0; i < nums1.length; i++) {int num = nums1[i]; // 当前要寻找下一个更大元素的数字// 遍历 nums2 来寻找 num 的下一个更大元素for (int j = 0; j < nums2.length; j++) {// 找到 num 在 nums2 中的位置if (nums2[j] == num) {int k = j + 1; // 从 num 的下一个位置开始查找// 遍历 nums2 中 num 之后的元素while (k < nums2.length) {// 如果找到比 num 更大的元素if (nums2[k] > num) {ans[i] = nums2[k]; // 更新结果数组break; // 找到下一个更大元素后退出循环}k++; // 否则继续查找}break; // 找到 num 后退出内层循环}}}return ans; // 返回结果数组
}

 

二、下一个更大元素2

题目:

给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1 。

示例 1:

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数; 
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。

示例 2:

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

思路:

本题的特点是数组是一个环形结构,数组中最后一个数的值需要由第二次遍历数组来确定,因此可以将数组进行复制拉长,同时超出数组长度的下标索引采用取模的方法进行定位

代码:

public int[] nextGreaterElements(int[] nums) {// 边界判断:如果 nums 为空或长度小于等于1,直接返回 -1if (nums == null || nums.length <= 1) {return new int[] { -1 };}int size = nums.length; // 数组的长度int[] result = new int[size]; // 结果数组,存放每个元素的下一个更大元素Arrays.fill(result, -1); // 初始化结果数组为 -1,表示默认没有找到更大的元素Stack<Integer> st = new Stack<>(); // 栈,用于存放 nums 数组的下标// 遍历数组 nums 两遍以处理循环的情况for (int i = 0; i < 2 * size; i++) {// 栈不为空且当前元素大于栈顶元素对应的元素while (!st.empty() && nums[i % size] > nums[st.peek()]) {result[st.peek()] = nums[i % size]; // 更新结果数组st.pop(); // 弹出栈顶元素}st.push(i % size); // 将当前元素的下标入栈}return result; // 返回结果数组
}

如果输入数组 numsnull 或者数组长度小于等于 1,直接返回一个结果数组 [-1]。因为对于空数组或单元素数组来说,不可能存在下一个更大的元素。

size 存储数组 nums 的长度。result 数组用于存储每个元素的下一个更大元素,初始时用 -1 表示默认没有找到更大的元素。st 是一个栈,用于存储 nums 中元素的下标。

通过遍历 2 * size 的范围来处理循环的情况。这种方法确保每个元素在循环后的数组中都有机会被检查一次。

nums[i % size] 使用模运算来处理数组的循环性质。

当栈不为空且当前元素 nums[i % size] 大于栈顶元素对应的值时,更新 result 数组,并将栈顶元素弹出。

将当前元素的下标入栈,以便后续可以找到比它大的元素。

返回存储了每个元素下一个更大元素的结果数组。

栈中元素的动态分析

以例子

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数; 
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。

初始化

  • 输入数组 nums = [1,2,1]
  • 结果数组 result = [-1, -1, -1](初始状态,所有值为 -1
  • 栈 st 为空

遍历过程

我们遍历 2 * size 次,其中 sizenums 的长度。对于输入 nums = [1,2,1]size3,因此我们遍历 6 次(从 05)。

第 1 次迭代(i = 0)

  • 当前元素是 nums[0 % 3] = nums[0] = 1
  • 栈为空,因此我们将 0 压入栈
  • 栈状态:[0]

第 2 次迭代(i = 1)

  • 当前元素是 nums[1 % 3] = nums[1] = 2
  • 栈不为空,且 2 > nums[st.peek()] = nums[0] = 1
    • 更新 result[0] = 2 (栈顶元素的下一个更大元素是 2
    • 弹出栈顶元素 0
  • 将 1 压入栈
  • 栈状态:[1]
  • 结果数组:[2, -1, -1]

第 3 次迭代(i = 2)

  • 当前元素是 nums[2 % 3] = nums[2] = 1
  • 栈不为空,且 1 不大于 nums[st.peek()] = nums[1] = 2
  • 将 2 压入栈
  • 栈状态:[1, 2]
  • 结果数组:[2, -1, -1]

第 4 次迭代(i = 3)

  • 当前元素是 nums[3 % 3] = nums[0] = 1
  • 栈不为空,且 1 不大于 nums[st.peek()] = nums[2] = 1
  • 将 3 % 3 = 0 压入栈
  • 栈状态:[1, 2, 0]
  • 结果数组:[2, -1, -1]

第 5 次迭代(i = 4)

  • 当前元素是 nums[4 % 3] = nums[1] = 2
  • 栈不为空,且 2 > nums[st.peek()] = nums[0] = 1
    • 更新 result[0] = 2 (栈顶元素的下一个更大元素是 2
    • 弹出栈顶元素 0
  • 栈不为空,且 2 > nums[st.peek()] = nums[2] = 1
    • 更新 result[2] = 2 (栈顶元素的下一个更大元素是 2
    • 弹出栈顶元素 2
  • 将 4 % 3 = 1 压入栈
  • 栈状态:[1]
  • 结果数组:[2, -1, 2]

第 6 次迭代(i = 5)

  • 当前元素是 nums[5 % 3] = nums[2] = 1
  • 栈不为空,且 1 不大于 nums[st.peek()] = nums[1] = 2
  • 将 5 % 3 = 2 压入栈
  • 栈状态:[1, 2]
  • 结果数组:[2, -1, 2]

总结

最终得到的结果数组是 [2, -1, 2],每个位置对应的下一个更大元素为:

  • 对于 nums[0] = 1,下一个更大的元素是 2
  • 对于 nums[1] = 2,在循环数组中没有更大的元素,因此结果是 -1
  • 对于 nums[2] = 1,下一个更大的元素是 2

三、柱状图中最大的矩形 

题目:

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例 1:

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

示例 2:

输入: heights = [2,4]
输出: 4

思路:

与接雨水类似,同时处理两边的元素,需要注意的是,题目中为了边界的处理需要对数组进行扩容操作

代码:

public int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<Integer>(); // 用于存储直方图的柱子下标// 数组扩容,在头和尾各加入一个高度为0的元素int[] newHeights = new int[heights.length + 2];newHeights[0] = 0; // 头部填充0newHeights[newHeights.length - 1] = 0; // 尾部填充0for (int index = 0; index < heights.length; index++) {newHeights[index + 1] = heights[index]; // 复制原数组到扩容后的数组}heights = newHeights; // 更新原数组为扩容后的数组st.push(0); // 初始将第一个填充的0的下标压入栈int result = 0; // 记录最大的矩形面积// 从第二个元素开始遍历(实际的第一个元素是新数组中的1)for (int i = 1; i < heights.length; i++) {// 比较当前柱子的高度与栈顶柱子的高度if (heights[i] > heights[st.peek()]) {st.push(i); // 当前柱子比栈顶柱子高,直接压栈} else if (heights[i] == heights[st.peek()]) {st.pop(); // 当前柱子与栈顶柱子高度相等,弹出栈顶,重新压栈st.push(i);} else {// 当前柱子低于栈顶柱子,弹出栈顶柱子,计算以弹出的柱子为高度的矩形面积while (heights[i] < heights[st.peek()]) {int mid = st.peek(); // 弹出的柱子下标st.pop();int left = st.peek(); // 弹出柱子左边最近的柱子下标int right = i; // 当前柱子下标int w = right - left - 1; // 宽度为右下标 - 左下标 - 1int h = heights[mid]; // 高度为弹出的柱子的高度result = Math.max(result, w * h); // 更新最大矩形面积}st.push(i); // 压入当前柱子的下标}}return result; // 返回最大矩形面积
}
  1. 数组扩容:在原数组的两端各加一个高度为0的柱子,简化处理边界情况。
  2. 栈的作用:用栈来保存柱子的下标,保证栈中柱子的高度是递增的。
  3. 面积计算:当发现当前柱子高度小于栈顶柱子的高度时,弹出栈顶柱子,并计算以该柱子为高度的矩形面积。
  4. 更新最大面积:每次计算出的矩形面积都与当前最大值比较,保持最大面积。

 

栈中元素的动态分析

以例子

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
  1. 初始化

    • 扩容后的数组:[0, 2, 1, 5, 6, 2, 3, 0]
    • 栈:[0](索引0的0)
  2. 遍历开始

    • i=1heights[1] = 2

      • 2 > 0(栈顶0),压栈。
      • 栈:[0, 1]
    • i=2heights[2] = 1

      • 1 < 2(栈顶1),弹出栈顶1,计算面积。
        • 高度:2
        • 左边界:0,右边界:2
        • 宽度:2 - 0 - 1 = 1
        • 面积:2 * 1 = 2
      • 继续弹出,0的矩形高度为0,面积为0,不更新结果。
      • 1压栈。
      • 栈:[0, 2]
    • i=3heights[3] = 5

      • 5 > 1(栈顶2),压栈。
      • 栈:[0, 2, 3]
    • i=4heights[4] = 6

      • 6 > 5(栈顶3),压栈。
      • 栈:[0, 2, 3, 4]
    • i=5heights[5] = 2

      • 2 < 6(栈顶4),弹出栈顶4,计算面积。
        • 高度:6
        • 左边界:3,右边界:5
        • 宽度:5 - 3 - 1 = 1
        • 面积:6 * 1 = 6
      • 2 < 5(栈顶3),弹出栈顶3,计算面积。
        • 高度:5
        • 左边界:2,右边界:5
        • 宽度:5 - 2 - 1 = 2
        • 面积:5 * 2 = 10
      • 继续弹出,2的矩形高度为1,面积1 * 1 = 1,不更新结果。
      • 2压栈。
      • 栈:[0, 2, 5]
    • i=6heights[6] = 3

      • 3 > 2(栈顶5),压栈。
      • 栈:[0, 2, 5, 6]
    • i=7heights[7] = 0

      • 0 < 3(栈顶6),弹出栈顶6,计算面积。
        • 高度:3
        • 左边界:5,右边界:7
        • 宽度:7 - 5 - 1 = 1
        • 面积:3 * 1 = 3
      • 0 < 2(栈顶5),弹出栈顶5,计算面积。
        • 高度:2
        • 左边界:2,右边界:7
        • 宽度:7 - 2 - 1 = 4
        • 面积:2 * 4 = 8
      • 继续弹出,0的矩形高度为0,面积为0,不更新结果。
      • 0压栈。
      • 栈:[7]
  3. 最终结果:最大矩形面积为10。

总结:栈中的元素是柱子的索引,保持柱子的高度递增。每次遇到较小的柱子时,弹出栈顶,计算相应的矩形面积,并更新最大面积。

今天的学习就到这里 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/407812.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C语言】进程和线程详解

目录 C语言进程和线程详解1. 进程和线程的对比2. 进程的基本概念2.1 进程的定义2.2 进程的特点2.3 进程的生命周期 3. 进程管理3.1 进程创建3.2 进程间通信&#xff08;IPC&#xff09;3.2.1 管道&#xff08;Pipe&#xff09; 4. 线程的基本概念4.1 线程的定义4.2 线程的特点 …

正则表达式匹配成对括号

匹配一对括号&#xff0c;用于在一个html文本中提取JSon 文本。例如 { “duration”:7599,"minBufferTime{second bracket }{third bracket} } 一对加粗的{} &#xff0c;而不要中间的{}。简单写法会出现错误匹配。 在.Net Framework的正则表达式中&#xff0c;提供了”…

大数据-100 Spark 集群 Spark Streaming DStream转换 黑名单过滤的三种实现方式

喜大普奔&#xff01;破百了&#xff01; 点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&a…

Java框架Shiro、漏洞工具利用、复现以及流量特征分析

Shiro流量分析 前言 博客主页&#xff1a; 靶场&#xff1a;Vulfocus 漏洞威胁分析平台 Shiro&#xff08;Apache Shiro&#xff09;是一个强大且灵活的开源安全框架&#xff0c;专为Java应用程序提供安全性解决方案。它由Apache基金会开发和维护&#xff0c;广泛应用于企业级…

毛利率承压连亏三年后一季度业绩暴增,百利天恒谋求A+H双上市

《港湾商业观察》施子夫 7月10日&#xff0c;四川百利天恒药业股份有限公司&#xff08;以下简称&#xff0c;百利天恒&#xff09;递表港交所主板&#xff0c;联席保荐机构高盛、摩根大通和中信证券。 此次递表港交所系百利天恒第二次谋求上市&#xff0c;若上市成功&#x…

PyTorch升级之旅——安装与基本知识

目录 一、安装 二、张量 创建tensor 张量的操作 广播机制 三、自动求导 四、并行计算 &#xff08;一&#xff09;网络结构分布到不同的设备中(Network partitioning) &#xff08;二&#xff09;同一层的任务分布到不同数据中(Layer-wise partitioning) &#xff08;…

GoModule

GOPATH 最早的就是GOPATH构建模式&#xff0c; go get下载的包都在path中的src目录下 src目录是源代码存放目录。 package mainimport ("net/http""github.com/gorilla/mux" )func main() {r : mux.NewRouter()r.HandleFunc("/hello", func(w h…

解决使用matplotlib不显示中文的问题

某季度某城市某天11点到12点气温变化图 import random x range(60) y_BeiJing [random.uniform(15,18) for i in x] plt.figure(figsize(20,8),dpi80) plt.plot(x,y_BeiJing) x_label ["11点{}分".format(i) for i in x] plt.xticks(x[::5],x_label[::5]) plt.yt…

【精选】基于微信小程序的地铁站点查询系统(全网独一无二,阿龙原创设计)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

C# x Unity面向对象补全计划 设计模式 之 实现一个简单的有限状态机

一个简单的有限状态机可以有如下内容 1.状态基类&#xff08;定义基本状态的方法&#xff0c;如进入&#xff08;Enter&#xff09;、执行&#xff08;Execute&#xff09;和退出&#xff08;Exit&#xff09;&#xff0c;同时可以在此声明需要被管理的对象&#xff09; 2.具体…

【精选】基于python的影片数据爬取与数据分析

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

软件设计师教程(第5版)第5章 软件工程基础知识(更新中)

5.1 软件工程概述 【软件工程】是指应用计算机科学、数学及管理科学等原理,以工程化的原则和方法来解决软件问题的工程&#xff0c;其目的是提高软件生产率、提高软件质量、降低软件成本。P239 5.1.1 计算机软件 计算机软件是指计算机系统中的【程序】及其【文档】。P240 【…

一文解决---IDEA汉化问题(含中英文切换)

一、英文->中文&#xff1a; ①.下载汉化包插件&#xff1a; 操作顺序&#xff1a;File->Settings->Plugins 在搜索框输入Chinese&#xff0c;然后找到 Chinese (Simplified) Language &#xff08;汉化插件&#xff09;&#xff0c;等待下载完→Install (安装)&…

OpenCV几何图像变换(9)仿射变换函数warpAffine()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 函数是应用一个仿射变换到图像上。 warpAffine 函数使用指定的矩阵对源图像进行仿射变换&#xff1a; dst ( x , y ) src ( M 11 x M 12 y M…

《机器学习》 决策树剪枝、树模型参数及案例演示

目录 一、决策树剪枝 1、什么是决策树剪枝&#xff1f; 2、如何剪枝 3、剪枝剪哪个位置的叶子结点 二、树模型参数及用法 1、参数种类 2、参数解释 1&#xff09;criterion&#xff1a;gini or entropy 2&#xff09;splitter&#xff1a;best or random 3&#xff0…

从心理学的角度,探究一下人类为什么爱玩游戏。(缓解压力、社交需求、 获得成就感)

文章目录 引言I 游戏中的美学和文化元素,是影响玩家心理状态的关键因素。音乐美工文化背景II 成年人对游戏的心理需求获得成就感社交需求缓解压力III 心流理论(Flow Theory)解释玩家虽受虐,但也其乐无穷的现象知识扩展: 心流知识扩展: 心流活动知识扩展:得性乐观(Learne…

新版本 | GreatSQL 8.0.32-26全新发布 增强“四高”诸多新特性

近日&#xff0c;GreatSQL开源数据库社区正式发布 GreatSQL 8.0.32-26新版本&#xff0c;在高可用、高性能、高兼容、高安全等诸多方面进行了特性增强&#xff0c;修复多个缺陷&#xff0c;并详细说明了多个典型应用场景下&#xff0c;升级/降级到GreatSQL 8.0.32-26的操作策略…

Linux自旋锁和读写锁

在前面的文章中我们已经介绍了有关互斥锁的概念与使用&#xff0c;本篇将开始介绍在 Linux 中的自旋锁和读写锁。这三种锁分别用于在不同的应用场景之中&#xff0c;其中互斥锁最为常用&#xff0c;但是我们需要了解一下其他的锁。 对于自旋锁和读写锁都介绍了其原理以及接口使…

游戏如何对抗 IL2cppDumper逆向分析

众所周知&#xff0c;Unity引擎中有两种脚本编译器&#xff0c;分别是 Mono 和 IL2CPP 。相较于Mono&#xff0c;IL2CPP 具备执行效率高、跨平台支持等优势&#xff0c;已被大多数游戏采用。 IL2CPP 模式下&#xff0c;可以将游戏 C# 代码转换为 C 代码&#xff0c;然后编译为…

GPT-4o System Card is released

GPT-4o System Card is released, including red teaming, frontier risk evaluations, and other key practices for industrial-strength Large Language Models. https://openai.com/index/gpt-4o-system-card/ 报告链接 企业级生成式人工智能LLM大模型技术、算法及案例实战…