代码随想录算法训练营第55天(py)| 单调栈 | 42. 接雨水*、84.柱状图中最大的矩形

42. 接雨水*

力扣链接
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
在这里插入图片描述

思路1 暴力

按列来计算。每一列雨水的高度,取决于,该列 左侧最高的柱子和右侧最高的柱子中,较矮的那个柱子的高度。
在这里插入图片描述

h = min(lHeight, rHeight) - height
class Solution:def trap(self, height: List[int]) -> int:res = 0for i in range(len(height)):if i == 0 or i == len(height)-1: continue # 如果是两端则不处理lHight = height[i-1]rHight = height[i+1]for j in range(i-1):if height[j] > lHight:lHight = height[j] # 找到左侧最高的for k in range(i+2,len(height)):if height[k] > rHight:rHight = height[k] # 找到右侧最高的res1 = min(lHight,rHight) - height[i]if res1 > 0:res += res1return res

但是这样会超时

思路2 双指针优化

把每一个位置的左边最高高度记录在一个数组上(maxLeft),右边最高高度记录在一个数组上(maxRight),这样就避免了重复计算。
对当前水柱i,他左边最高的柱子为maxLeft[i],右边最高的柱子为maxRight[i]

maxLeft[i] = max(height[i], maxLeft[i - 1])
maxRight[i] = max(height[i], maxRight[i + 1]);
class Solution:def trap(self, height: List[int]) -> int:maxleft = [0] * len(height)maxright = [0] * len(height)# 记录左侧最大柱子高度maxleft[0] = height[0]for i in range(len(height)):maxleft[i] = max(height[i], maxleft[i-1])# 记录右侧最大柱子高度maxright[-1] = height[-1]for i in range(len(height)-2, -1, -1):maxright[i] = max(height[i], maxright[i+1])res = 0for i in range(len(height)):res1 = min(maxleft[i],maxright[i]) - height[i]if res1 > 0:res += res1return res

思路3 单调栈

在这里插入图片描述
将每条柱子下标依次压栈
一旦发现添加的柱子高度大于栈头元素了,此时就出现凹槽了,栈头元素就是凹槽底部的柱子,栈头第二个元素就是凹槽左边的柱子,而添加的元素就是凹槽右边的柱子。
从栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序。
求一个元素右边第一个更大元素,单调栈就是递增的;
求一个元素右边第一个更小元素,单调栈就是递减的。

遇到相同的元素,更新栈内下标,就是将栈里元素(旧下标)弹出,将新元素(新下标)加入栈中。要求宽度的时候 如果遇到相同高度的柱子,需要使用最右边的柱子来计算宽度。
在这里插入图片描述
在这里插入图片描述
有三种情况:
情况一:当前遍历的元素(柱子)高度小于栈顶元素的高度 height[i] < height[st.top()]
情况二:当前遍历的元素(柱子)高度等于栈顶元素的高度 height[i] == height[st.top()]
情况三:当前遍历的元素(柱子)高度大于栈顶元素的高度 height[i] > height[st.top()]
先将下标0的柱子压栈,然后遍历height。
如果当前柱子低于栈顶,则入栈(因为要保持栈顶方向的递减)
如果当前柱子等于栈顶,则更新栈顶元素,先出栈再压栈
如果当前柱子高于栈顶,则出栈,记为mid(遇到凹槽了),此时栈顶为凹槽左,当前元素为凹槽右

显而易见,水的高度和宽度为:

h = min(height[st.pop()],height[i])-height[mid] # min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度
w = i - st.top() - 1 # 凹槽右边的下标 - 凹槽左边的下标 - 1
class Solution:def trap(self, height: List[int]) -> int:stack = [0]res = 0for i in range(len(height)):if height[i]<height[stack[-1]]:stack.append(i)elif height[i] == height[stack[-1]]:stack.pop()stack.append(i)else:while stack and height[i] > height[stack[-1]]:mh = height[stack[-1]]stack.pop()if stack:rh = height[i]lh = height[stack[-1]]h = min(rh, lh) - mhw = i - stack[-1] -1res += h*wstack.append(i)return res

84.柱状图中最大的矩形

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

求在该柱状图中,能够勾勒出来的矩形的最大面积。
在这里插入图片描述

思路1 双指针

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:size = len(heights)minleft = [0] * sizeminright = [0] * size# 记录每个柱子左边第一个矮子minleft[0] = -1# 防止死循环for i in range(size):t = i-1while t>=0 and heights[t]>=heights[i]: #不断向左寻找,没找到就尝试这个高柱子自己的次级柱子t = minleft[t]minleft[i] = t# 记录每个柱子右边第一个矮子minright[-1] = sizefor i in range(size-2, -1, -1):t = i+1while t<size and heights[t]>=heights[i]: #不断向右寻找,没找到就尝试这个高柱子自己的次级柱子t = minright[t]minright[i] = tres = 0for i in range(size):res1 = heights[i] * (minright[i] - minleft[i] - 1)res = max(res1,res)return res

思路2 单调栈

本题是要找每个柱子左右两边第一个小于该柱子的柱子,所以从栈头(元素从栈头弹出)到栈底的顺序应该是从大到小的顺序
在这里插入图片描述
逻辑和接雨水差不多,就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度。

找每个柱子左右侧的第一个高度值小于该柱子的柱子
单调栈:栈顶到栈底:从大到小(每插入一个新的小数值时,都要弹出先前的大数值)
栈顶,栈顶的下一个元素,即将入栈的元素:这三个元素组成了最大面积的高度和宽度

有三种情况:
情况一:当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
情况二:当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三:当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
此外,还需要在height首尾各加一个0,以防跳过

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:res = 0stack = [0]heights.insert(0,0)heights.append(0)for i in range(1, len(heights)):if heights[i] > heights[stack[-1]]:stack.append(i)elif heights[i] == heights[stack[-1]]:stack.pop()stack.append(i)else:while stack and heights[i] < heights[stack[-1]]:mid = stack[-1]stack.pop()if stack:left = stack[-1]right = iw = right - left - 1h = heights[mid]res = max(res, w * h)stack.append(i)return res

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

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

相关文章

Study--Oracle-05-Oracler体系结构

一、oracle 体系概览 Oracle数据库的体系结构通常包括以下主要组件&#xff1a; 1、实例&#xff08;Instance&#xff09;&#xff1a;运行数据库的软件环境&#xff0c;包括内存结构&#xff08;SGA&#xff09;和进程结构&#xff08;Background Processes and User Proces…

【电路笔记】-A类放大器

A类放大器 文章目录 A类放大器1、A类放大器概述2、A类放大器基本通用发射极配置3、变压器耦合配置4、总结在 放大器类型简介的文章中,我们介绍了不同类别的放大器。 在本文中,我们将更详细地介绍A类放大器。 在介绍不同的A类放大器配置前,首先的是要记住放大器类别的选择标…

从新手到高手:Scala函数式编程完全指南,Scala 数据类型(4)

1、Scala 数据类型 Scala 与 Java有着相同的数据类型&#xff0c;下表列出了 Scala 支持的数据类型&#xff1a;

【程序大侠传】异步架构应用回调数据接收接口偶发NPE

前序 在这片浩瀚的代码江湖中&#xff0c;各大门派林立&#xff0c;各自修炼独门绝技&#xff0c;江湖中的侠士们分别担任着开发、测试、产品和运维的角色&#xff0c;共同守护着这片数字化的疆域。 开发门派&#xff1a;代码剑宗 代码剑宗的弟子们精通各种编程语言&#xff…

【性能优化】Android冷启动优化

文章目录 常见现象APP的启动流程计算启动时间Displayed Timeadb dump 启动优化具体策略总结参考链接 常见现象 各种第三方工具初始化和大量业务逻辑初始化&#xff0c;影响启动时间&#xff0c;导致应用启动延迟、卡顿等现象 APP的启动流程 加载和启动应用程序&#xff1b; …

PTFE铲子聚四氟乙烯物料特氟龙铲粉料铲耐酸碱塑料药铲

四氟铲子主要适用于药厂、药企、医药行业专用&#xff0c;用于粉末状及颗粒物状样品的铲取和搅匀等。因为粉料物料对铲子材质要求无污染、本底值低&#xff0c;所以四氟材质成为选择。 其主要特点有&#xff1a; 1.外观纯白色。 2.耐高低温性&#xff1a;可使用温度-200℃&am…

docker 部署jitsi meet

1. 部署环境&#xff1a; 1.1 vm 虚拟机 安装的 centos 7 1.2 centos7安装docker 和 docker-compose 2.docker命令 官网部署文档地址&#xff1a;&#xff08;文档地址有可能失效&#xff09; Self-Hosting Guide - Docker | Jitsi Meet 2.1Download and extract the late…

基于yolo的物体识别坐标转换

一、模型简介: 1.1、小孔成像模型简图如下:不考虑实际相机中存在的场曲、畸变等问题 相对关系为: 为了表述与研究的方便,我们将像面至于小孔之前,且到小孔的距离仍然是焦距f,这样的模型与原来的小孔模型是等价的 相对关系为: 二、坐标系简介: **世界坐标系(world coo…

旋转变压器软件解码simulink仿真

1.介绍 旋转变压器是一种精密的位置、速度检测装置&#xff0c;尤其适用于高温、严寒、潮湿、高速、振动等环境恶劣、旋转编码器无法正常工作的场合。旋转变压器在使用时并不能直接提供角度或位置信息&#xff0c;需要特殊的激励信号和解调、计算措施&#xff0c;才能将旋转变压…

Element UI搭建使用过程

本章内容基于上一篇---Vue-cli搭建项目基础版 Vue-cli搭建项目----基础版-CSDN博客 官网地址:Element - The worlds most popular Vue UI framework 介绍:完全基于Vue.js ,用于快速搭建用户界面. 第一步:安装ElementUI 在终端输入 npm i element-ui -S 在main.js输入 …

Golang-map理解

golang-map语雀笔记整理 map的底层实现hmapbmap map是如何做到O(1)的复杂度的&#xff1f;map扩容策略 师兄问题回答 map的底层实现 hmap hmap的结构体核心字段有&#xff1a;buckets 桶数组地址&#xff0c; B 定位值&#xff0c;桶的数目是2^B个&#xff0c; count 当前map的…

一个 API 客户端和一份 TS 学习手册

第75期&#xff1a; Insomnia&#xff1a;超好看的 API 客户端 项目介绍&#xff1a; 一款适用于 GraphQL、REST、WebSockets 和 gRPC 的开源 API 客户端&#xff0c;颜值超高。 跨平台&#xff0c;支持 Mac、Windows 和 Linux。但不支持网页版&#xff0c;需要下载客户端。…

【AI编译器】triton学习:矩阵乘优化

Matrix Multiplication 主要内容&#xff1a; 块级矩阵乘法 多维指针算术 重新编排程序以提升L2缓存命 自动性能调整 Motivations 矩阵乘法是当今高性能计算系统的一个关键组件&#xff0c;在大多数情况下被用于构建硬件。由于该操作特别复杂&#xff0c;因此通常由软件提…

【论文复现|智能算法改进】基于自适应动态鲸鱼优化算法的路径规划研究

目录 1.算法原理2.改进点3.结果展示4.参考文献5.代码获取 1.算法原理 SCI二区|鲸鱼优化算法&#xff08;WOA&#xff09;原理及实现【附完整Matlab代码】 2.改进点 非线性收敛因子 WOA 主要通过控制系数向量 A 来决定鲸鱼是搜索猎物还是捕获猎物&#xff0c;即系数向量 A 可…

七月论文审稿GPT第5版:拿我司七月的早期paper-7方面review数据集微调LLama 3

前言 llama 3出来后&#xff0c;为了通过paper-review的数据集微调3&#xff0c;有以下各种方式 不用任何框架 工具 技术&#xff0c;直接微调原生的llama 3&#xff0c;毕竟也有8k长度了 效果不期望有多高&#xff0c;纯作为baseline通过PI&#xff0c;把llama 3的8K长度扩展…

应用案例 | 如何监测高价值货物在物流运输过程中受到的振动和冲击?全面保障货物安全

一、货物运输 不同种类的货物对运输的要求不同&#xff0c;钢铁、煤炭、矿石等大宗物资通常对运输要求较低&#xff0c;而电子产品、IT 产品、家电等高价值敏感类货物则更强调运输的安全性和时效性&#xff0c;往往希望能尽可能安全和快速送达这类货物&#xff0c;使之尽快进入…

SpringBoot:SpringBoot中调用失败如何重试

一、引言 在实际的应用中&#xff0c;我们经常需要调用第三方API来获取数据或执行某些操作。然而&#xff0c;由于网络不稳定、第三方服务异常等原因&#xff0c;API调用可能会失败。为了提高系统的稳定性和可靠性&#xff0c;我们通常会考虑实现重试机制。 Spring Retry为Spri…

Django 一对多关系

1&#xff0c;创建 Django 应用 Test/app9 django-admin startapp app9 2&#xff0c;注册应用 Test/Test/settings.py 3&#xff0c;添加应用路由 Test/Test/urls.py from django.contrib import admin from django.urls import path, includeurlpatterns [path(admin/,…

uniApp获取实时定位

通过你获取的key放到项目manifest.json里面&#xff0c;对应填写你所需要的key值&#xff0c;还有高德用户名 用户名&#xff1a; key值的位置&#xff1a; 代码&#xff1a; html: <view class"intList pdNone"><view class"label">详细地…

使用 nvm 管理 Node 版本及 pnpm 安装

文章目录 GithubWindows 环境Mac/Linux 使用脚本进行安装或更新Mac/Linux 环境变量nvm 常用命令npm 常用命令npm 安装 pnpmNode 历史版本 Github https://github.com/nvm-sh/nvm Windows 环境 https://nvm.uihtm.com/nvm.html Mac/Linux 使用脚本进行安装或更新 curl -o- …