Day51 算法记录| 动态规划 18(单调栈)

单调栈

  • 739. 每日温度
  • 496.下一个更大元素 I
  • 503. 下一个更大元素 II
  • 42. 接雨水
  • 84. 柱状图中最大的矩形

单调栈:找最近的比他大的值
最近大的值:需要一个单调递减的栈(大于栈顶元素就弹出)
最近最小值:单调递减栈

方向: 右边,从后往前遍历 左边:从头遍历

739. 每日温度

单调栈:找最近的比他大的值
我最开始也是两层for循环,严重超时
通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] res = new int[n];Deque<Integer> stack = new LinkedList<>();for(int i=0;i<n;i++){while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){int index = stack.pop();res[index] = i - index;}stack.push(i);}return res;}
}

496.下一个更大元素 I

我自己的思路:
直接用上面的方法,求出原有的nums2 [ ] 对应的res2[ ],里面存放的是下一个大的值
然后两层for循环遍历,求出nums1[ ]对应的res1[ ]

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int n = nums1.length;int[] res1 = new int[n];int[] res2 = next(nums2);for(int i=0;i<n;i++){for(int j=0;j<nums2.length;j++){if(nums1[i] == nums2[j]){res1[i] = res2[j];}}}return res1;}private int[] next(int[] nums2){int n = nums2.length;int[] res = new int[n];Arrays.fill(res,-1);Deque<Integer> stack = new LinkedList<>();for(int i=0;i<n;i++){while(!stack.isEmpty()&&nums2[i]>nums2[stack.peek()]){int index = stack.pop();res[index] =nums2[i];}stack.push(i);}return res;}}

单调栈和哈希表

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Deque<Integer> stack = new LinkedList<>();HashMap<Integer,Integer> map = new HashMap<>();// 键放nums2的元素,值放比它大的最近的元素for(int num :nums2){while(!stack.isEmpty()&& num>stack.peek()){map.put(stack.pop(), num);}stack.push (num);}int[] res = new int[nums1.length];for(int i=0;i<nums1.length;i++){res[i] = map.getOrDefault(nums1[i],-1);}return res;}
}

503. 下一个更大元素 II

和739一模一样,只是多了扩大数组这一步

在这里插入图片描述

class Solution {public int[] nextGreaterElements(int[] nums) {Deque<Integer> stack = new LinkedList<>();int n = nums.length;int[] newArr = Arrays.copyOf(nums, 2*n); //newArr = [nums,nums] 扩展成两倍System.arraycopy(nums, 0, newArr, n, n);int[] res = new int[2*n]; //右边最近的大值Arrays.fill(res,-1);for(int i=0;i<2*n;i++){while(!stack.isEmpty()&&newArr[stack.peek()]<newArr[i]){res[stack.pop()] = newArr[i];}stack.push(i);}int[] newRes =  Arrays.copyOf(res, n); // 只需要前n个数据return newRes;}
}

不需要扩展了,想要遍历前面的数据就用:i%n来表示循环,i<2n,循环两次

class Solution {public int[] nextGreaterElements(int[] nums) {Deque<Integer> stack = new LinkedList<>();int n = nums.length;int[] res = new int[n];Arrays.fill(res,-1);for(int i=0;i<2*n;i++){int num = nums[i%n];while(!stack.isEmpty()&&nums[stack.peek()]< num){res[stack.pop()] = num;}if(i<n){stack.push(i);}}return res;}
}

42. 接雨水

两种方法都讲解的超级好呀!!!

方法一:
当前位置能接到的水 = MIN(前面的最大高度, 后面的最大高度)- 当前的高度

class Solution {public int trap(int[] height) {int n = height.length;int[] pre = new int[n]; //int[] next = new int[n];pre[0] = height[0];for(int i=1;i<n;i++){pre[i] = Math.max(pre[i-1],height[i]);}next[n-1] = height[n-1];for(int j=n-2;j>=0;j--){next[j]=Math.max(next[j+1],height[j]);}int ans =0;for(int i=0;i<n;i++){ans +=Math.min(pre[i],next[i]) - height[i];}return ans;}
}

思路二:
如果前缀最大值 < 后缀最大值, 左边 l e f t left left木桶的容量就是 前缀最大值 - h e i g h t [ i ] height[i] height[i]
如果前缀最大值 > 后缀最大值, 右边 r i g h t right right木桶的容量就是 后缀最大值 - h e i g h t [ i ] height[i] height[i]

class Solution {public int trap(int[] height) {int left =0;int right = height.length-1;int ans = 0;int pre = 0;int suf =0;while(left<=right){pre = Math.max(height[left],pre);suf = Math.max(height[right],suf);if(pre<suf){ans += pre - height[left];left++;}else{ans += suf-height[right];right--;}}return ans;}
}

方法三:单调栈

找左右比自己大的元素, 当前位置的面积= (矮柱子-当前高度)*两柱子之间的宽度

class Solution {public int trap(int[] height) {Deque<Integer> stack = new LinkedList<>();int ans =0;for(int i=0;i<height.length;i++){while(!stack.isEmpty()&& height[i] > height[stack.peek()]){int cur = height[stack.pop()];if(!stack.isEmpty()){int h = Math.min(height[stack.peek()],height[i]);ans += (h-cur)*(i-stack.peek()-1); //是两柱子之间的高度,所以-1}}stack.push(i);}return ans;}
}

84. 柱状图中最大的矩形

和上一题思路类似,找到左右两边比自己小的元素
比自己小的:所以需要单调递增的栈
每个点对应的最大面积 m a x max max =( 右边最近小 - 左边最近小 -1) * 当前高度

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;int[] newH = new int[n+2];System.arraycopy(heights,0,newH,1,n);int ans =0;Deque<Integer> stack = new LinkedList<>();for(int i=0;i<n+2;i++){while(!stack.isEmpty() && newH[i]<newH[stack.peek()]){int cur = newH[stack.pop()];if(!stack.isEmpty()){int l = stack.peek(); //左边比它低的ans = Math.max(ans,cur*(i-l-1));}}stack.push(i);}return ans;}
}

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

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

相关文章

idea-常用插件汇总

idea-常用插件汇总 码云插件 这个插件是码云提供的ps-码云是国内的一款类似github的代码托管工具。 Lombok Lombok是一个通用Java类库&#xff0c;能自动插入编辑器并构建工具&#xff0c;简化Java开发。通过添加注解的方式&#xff0c;不需要为类编写getter或setter等方法…

记一次 .NET 某物流API系统 CPU爆高分析

一&#xff1a;背景 1. 讲故事 前段时间有位朋友找到我&#xff0c;说他程序CPU直接被打满了&#xff0c;让我帮忙看下怎么回事&#xff0c;截图如下&#xff1a; 看了下是两个相同的程序&#xff0c;既然被打满了那就抓一个 dump 看看到底咋回事。 二&#xff1a;为什么会打…

【雕爷学编程】Arduino动手做(181)---Maixduino AI开发板11

37款传感器与执行器的提法&#xff0c;在网络上广泛流传&#xff0c;其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块&#xff0c;依照实践出真知&#xff08;一定要动手做&#xff09;的理念&#xff0c;以学习和交流为目的&am…

中断管理

其实&#xff0c;关于中断的概念和定义在之前已经反复学习和实践了&#xff0c;这节主要讲和FreeRTOS相关的中断知识。 中断优先级 任何中断的优先级都大于任务&#xff01; 在我们的操作系统&#xff0c;中断同样是具有优先级的&#xff0c;并且我们也可以设置它的优先级&a…

汽车EBSE测试流程分析(四):反思证据及当前问题解决

EBSE专题连载共分为“五个”篇章。此文为该连载系列的“第四”篇章&#xff0c;在之前的“篇章&#xff08;三&#xff09;”中已经结合具体研究实践阐述了“步骤二&#xff0c;通过系统调研确定改进方案”等内容。那么&#xff0c;在本篇章&#xff08;四&#xff09;中&#…

elementUI全屏loading的使用(白屏的解决方案)

官网中有使用方法&#xff0c;但是我实际上手之后会出现白屏&#xff0c;解决办法如下&#xff1a; <el-button type"text" size"small" click"delRow(scope)"> 删除</el-button>loading: false, // loading 动画loadingInstance…

windows图标白了,刷新图标

1.进入C盘&#xff0c;user(用户文件夹)&#xff0c;进入当前用户文件夹&#xff0c;再进入隐藏文件夹(AppDada)&#xff0c;最后进入Local 2.删除Local文件夹里的IconCache.db文件 3.重启资源管理器 -------------------------------------------- 或者创建bat文件&#xf…

爬虫008_流程控制语句_if_if else_elif_for---python工作笔记026

然后我们再来看一下这里的,判断,可以看到 再看一个判断,这里的布尔类型 第二行有4个空格,python的格式 注意这里,输入的age是字符串,需要转一下才行 int可以写到int(intput("阿斯顿法师打发地方")) 这样也可以

无涯教程-Perl - Subroutines(子例程)

定义子程序 Perl编程语言中 Subroutine子程序定义的一般形式如下: sub subroutine_name {body of the subroutine } 调用该Perl Subroutine的典型方式如下- subroutine_name( list of arguments ); 在Perl 5.0之前的版本中&#xff0c;调用 Subroutine的语法略有不同&…

认识Webpack插件Plugin;CleanWebpackPlugin插件;HtmlWebpackPlugin;DefinePlugin;Mode模式

目录 1_认识插件Plugin2_CleanWebpackPlugin3_HtmlWebpackPlugin4_DefinePlugin4.1_介绍4.2_DefinePlugin的使用 5_Mode模式 1_认识插件Plugin Webpack的另一个核心是Plugin&#xff0c;官方有这样一段对Plugin的描述&#xff1a; While loaders are used to transform certai…

运算放大器(二):恒流源

一、实现原理 恒流源的输出电流能够在一定范围内保持稳定&#xff0c;不会随负载的变化而变化。 通过运放&#xff0c;将输入的电压信号转换成满足一定关系的电流信号&#xff0c;转换后的电流相当一个输出可调的简易恒流源。 二、电路结构 常用的恒流源电路如…

HCIP期中实验

考试需求 1 、该拓扑为公司网络&#xff0c;其中包括公司总部、公司分部以及公司骨干网&#xff0c;不包含运营商公网部分。 2 、设备名称均使用拓扑上名称改名&#xff0c;并且区分大小写。 3 、整张拓扑均使用私网地址进行配置。 4 、整张网络中&#xff0c;运行 OSPF 协议…

Jenkins工具系列 —— 插件 钉钉发送消息

文章目录 安装插件 Ding TalkJenkins 配置钉钉机器人钉钉APP配置项目中启动钉钉通知功能 安装插件 Ding Talk 点击 左侧的 Manage Jenkins —> Plugins ——> 左侧的 Available plugins Jenkins 配置钉钉机器人 点击 左侧的 Manage Jenkins &#xff0c;拉到最后 钉…

数字化时代,如何做好用户体验与应用性能管理

引言 随着数字化时代的到来&#xff0c;各个行业的应用系统从传统私有化部署逐渐转向公有云、行业云、微服务&#xff0c;这种变迁给运维部门和应用部门均带来了较大的挑战。基于当前企业 IT 运维均为多部门负责&#xff0c;且使用多种运维工具&#xff0c;因此&#xff0c;当…

使用socket实现UDP版的回显服务器

文章目录 1. Socket简介2. DatagramSocket3. DatagramPacket4. InetSocketAddress5. 实现UDP版的回显服务器 1. Socket简介 Socket&#xff08;Java套接字&#xff09;是Java编程语言提供的一组类和接口&#xff0c;用于实现网络通信。它基于Socket编程接口&#xff0c;提供了…

无人机管控平台,推动电力巡检管理水平提升

各地区无人机作业水平和管理水平存在参差不齐&#xff0c;电力巡检管理要求与业务发展水平不匹配的问题。同时&#xff0c;巡检数据的存储和管理分散&#xff0c;缺乏有效的整合与共享手段&#xff0c;使得内外业脱节&#xff0c;没有形成统一应用和闭环管理。这就导致巡检数据…

深度学习Redis(2):持久化

前言 在上一篇文章中&#xff0c;介绍Redis的内存模型&#xff0c;从这篇文章开始&#xff0c;将依次介绍Redis高可用相关的知识——持久化、复制(及读写分离)、哨兵、以及集群。 本文将先说明上述几种技术分别解决了Redis高可用的什么问题&#xff1b;然后详细介绍Redis的持…

每日汇评:由于美国就业数据强劲,黄金可能恢复下行趋势

1、美国非农就业数据公布前&#xff0c;金价试图从三周低点反弹&#xff1b; 2、美国经济数据喜忧参半&#xff0c;推动美元和美债收益率回落&#xff1b; 3、金价上行空间有限&#xff0c;因日技术面走势偏空&#xff1b; 金价又将下跌一周&#xff0c;周五有望创下六周以来…

2024年杭电MBA项目招生信息全面了解

2024年全国管理类硕士联考备考已经到了最火热的阶段&#xff0c;不少考生开始持续将注意力集中在备考的规划中&#xff01;杭州达立易考教育整合浙江省内的MBA项目信息&#xff0c;为大家详细梳理了相关报考参考内容&#xff0c;方便大家更好完成择校以及针对性的备考工作。本期…

微信小程序 - scroll-view组件之上拉加载下拉刷新(解决上拉加载不触发)

前言 最近在做微信小程序项目中&#xff0c;有一个功能就是做一个商品列表分页限流然后实现上拉加载下拉刷新功能&#xff0c;遇到了一个使用scroll-viwe组件下拉刷新事件始终不触发问题&#xff0c;网上很多说给scroll-view设置一个高度啥的就可以解决&#xff0c;有些人设置了…