代码随想录算法训练营第六十天| 84.柱状图中最大的矩形

文档讲解:代码随想录

视频讲解:代码随想录B站账号

状态:看了视频题解和文章解析后做出来了

84.柱状图中最大的矩形

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights.insert(0, 0)heights.append(0)stack = [0]result = 0for i in range(1, len(heights)):while stack and heights[i] < heights[stack[-1]]:mid_height = heights[stack[-1]]stack.pop()if stack:# area = width * heightarea = (i - stack[-1] - 1) * mid_heightresult = max(area, result)stack.append(i)return result
  • 时间复杂度:O(N)
  • 空间复杂度:O(N)

和雨水那道题差不多,这道题的区别在于单调栈里的元素是栈头到栈尾从大到小,这样计算出最大的长方形面积。

只有栈里从大到小的顺序,才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子:

这道题还需要在input数组的头尾分别加上高度为0的bar,这样确保第一个出栈的元素可以计算到面积,以及如果单调栈里都是从大到小(这样就不会有出栈了)最后的0保证一定有出栈来计算面积。

其他的和接雨水差不多,都是先pop然后记录pop的值作为高度,当前元素减去栈顶的下标再减一作为宽度,这两个相乘并不断更新result来计算最大的长方形面积。

代码随想录刷题总结

虽然只有60天的刷题时间,但这段经历充满了曲折。从最初的激情到中途的疲惫,再到后来习惯的形成,如果没有这个训练营和陪我一起刷题的小伙伴,我可能还在每天挣扎刷题的阶段。

解决每一种题目的关键在于掌握它想考察的核心思想和解题的关键方法。以回溯法为例,虽然N皇后问题看起来很复杂,但只要掌握了回溯的基本步骤,明确每个环节,代码实现就顺其自然了。一种题型的解题方法常常可以启发解决其他题型,即使是难题,也不过是基础题型的变体而已。因此,从简单题开始逐步提升的策略也是非常有效的。

刷题时最忌讳的是对问题一知半解。我之前刷题时,一旦没思路就会看别人的解答,然后模仿搬过来,随意理解别人的思路,只要通过就认为完成了。这种方法是不可取的,因为解答只提供了大致的思路,无法涵盖所有细节和考虑。

代码中的每一个细节都可能是解题的关键。比如二分查找,for循环中的范围区间虽看似简单,实际上却是掌握这类题型的核心概念。再如动态规划中的背包问题,两个循环的顺序看似显而易见,但物品和背包的循环顺序,以及为什么有时候需要逆序循环,都是值得深入研究的。

我即将开始第二轮的刷题,希望这次能更加注重细节,争取做到对每一题的核心概念都有更加深入的理解。

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

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

相关文章

java操作windows系统功能案例(二)

1、打印指定文件 可以使用Java提供的Runtime类和Process类来打印指定文件。以下是一个示例代码&#xff1a; import java.io.File; import java.io.IOException;public class PrintFile {public static void main(String[] args) {if (args.length ! 1) {System.out.println(…

NFT Insider115:The Sandbox开设元宇宙Diorama快闪店,​YGG Web3 游戏峰会已开幕

引言&#xff1a;NFT Insider由NFT收藏组织WHALE Members、BeepCrypto联合出品&#xff0c;浓缩每周NFT新闻&#xff0c;为大家带来关于NFT最全面、最新鲜、最有价值的讯息。每期周报将从NFT市场数据&#xff0c;艺术新闻类&#xff0c;游戏新闻类&#xff0c;虚拟世界类&#…

时间序列预测实战(二十一)PyTorch实现TCN卷积进行时间序列预测(专为新手编写的自研架构)

一、本文介绍 本篇文章给大家带来的是利用我个人编写的架构进行TCN时间序列卷积进行时间序列建模&#xff08;专门为了时间序列领域新人编写的架构&#xff0c;简单不同于市面上大家用GPT写的代码&#xff09;&#xff0c;包括结果可视化、支持单元预测、多元预测、模型拟合效…

【深度学习】因果推断与机器学习

2023年初是人工智能爆发的里程碑式的重要阶段&#xff0c;以OpenAI研发的GPT为代表的大模型大行其道&#xff0c;NLP领域的ChatGPT模型火爆一时&#xff0c;引发了全民热议。而最新更新的GPT-4更是实现了大型多模态模型的飞跃式提升&#xff0c;它能够同时接受图像和文本的输入…

通过navicat工具将excel文件导入数据库的表中

文章目录 1.navicat可视化工具2. 导入文件 1.navicat可视化工具 这里使用的是navicat数据库可视化工具&#xff0c;不是直接通过数据库指令导入的 前提是连接好数据库&#xff0c;建立好表&#xff0c;如下图&#xff0c;test为连接名&#xff0c;随便起&#xff0c;data为数据…

windows系统玩游戏找不到d3dx9_35.dll缺失的解决方法

分享一个我们在打开游戏或许软件过程中遇到的问题——“由于找不到d3dx9_35.dll,无法继续执行代码”的五个修复方案。这个问题可能会影响到我们的工作和娱乐效率&#xff0c;甚至可能导致工作的延期。因此&#xff0c;我希望通过今天的文章&#xff0c;能够帮助大家更好地解决这…

STL: 容器适配器stack 与 queue

目录 1.容器适配器 1.1 STL标准库中stack和queue的底层结构 1.2 deque的简单介绍(了解) 1.2.1 deque的原理介绍 1.2.2 deque的缺陷 1.2.3 为什么选择deque作为stack和queue的底层默认容器 2. stack的介绍和使用 2.1 stack的介绍 2.2 stack的使用 2.3 利用deque模拟实现…

c++基本常见错误总结

我们无论是在学习中还是在工作当中&#xff0c;总是会遇到各种各样的c编译错误问题&#xff0c;经常会有一种情况就是上一次好像遇到过这种问题&#xff0c;但是就是想不起来了&#xff08;我就是这样&#xff09;所以下面这一篇文章就是总结自己遇到的编译以及运行错误。 注意…

宝塔面板安装搭建DiscuzQ论坛教程与小程序上架发布后的展示效果

DiscuzQ论坛小程序上架发布后的展示效果&#xff1a; 1、需要用到的环境&#xff1a; php7.2 mysql5.7或者MariaDB 10.2(我安装用的mysql8.0) php除了必要的一些扩展外&#xff0c;还需要启用readlink、symlink函数等&#xff0c;具体看官方说明&#xff0c;安装的时候也会提醒…

【鸿蒙应用ArkTS开发系列】- 云开发入门实战二 实现省市地区三级联动地址选择器组件(上)

目录 概述 云数据库开发 一、创建云数据库的对象类型。 二、预置数据&#xff08;为对象类型添加数据条目&#xff09;。 三、部署云数据库 云函数实现业务逻辑 一、创建云函数 二、云函数目录讲解 三、创建resources目录 四、获取云端凭据 五、导出之前创建的元数据…

【Vue】@keyup.enter @v-model.trim的用法

目录 keyup.enter v-model.trim 情景一&#xff1a; 情景二&#xff1a; keyup.enter 作用&#xff1a;监听键盘回车事件 上一篇内容&#xff1a; 记事本 https://blog.csdn.net/m0_67930426/article/details/134630834?spm1001.2014.3001.5502 这里有个添加任务的功能&…

使用opencv实现图像滤波

1 图像滤波介绍 滤波是信号和图像处理中的基本任务之一&#xff0c;其旨在有选择地提取图像的某些特征&#xff0c;可以用于在给定应用程序的上下文中传达重要信息&#xff0c;例如&#xff0c;去除图像中的噪声、提取所需的视觉特征、图像重采样等。 1.1 图像滤波理论 图像…

R语言实现Lasso回归

一、Lasso回归 Lasso 回归&#xff08;Least Absolute Shrinkage and Selection Operator Regression&#xff09;是一种用于线性回归和特征选择的统计方法。它在回归问题中加入了L1正则化项&#xff0c;有助于解决多重共线性&#xff08;多个特征高度相关&#xff09;和特征选…

C语言——写一个简单函数,找两个数中最大者

#include <stdio.h>int max( int a, int b ) { return a>b ? a:b; }int main() { int a, b;printf("输入两个数:\n");scanf("%d %d", &a, &b);printf("max %d\n", max(a, b));return 0; }输出结果&#xff1a;

C#文件基本操作(判断文件是否存在、创建文件、复制或移动文件、删除文件以及获取文件基本信息)

目录 一、判断文件是否存在 1.File类的Exists()方法 2.FileInfo类的Exists属性 二、创建文件 1.File类的Create()方法 2.FileInfo类的Create()方法 三、复制或移动文件 1.File类的Copy()方法 2.File类的Move()方法 3.FileInfo类的CopyTo()方法 四、删除文件 1.File…

大数据基础设施搭建 - Hive

文章目录 一、上传压缩包二、解压压缩包三、配置环境变量四、初始化元数据库4.1 配置MySQL地址4.2 拷贝MySQL驱动4.3 初始化元数据库4.3.1 创建数据库4.3.2 初始化元数据库 五、启动元数据服务metastore5.1 修改配置文件5.2 启动/关闭metastore服务 六、启动hiveserver2服务6.1…

MacOS + Android Studio 通过 USB 数据线真机调试

环境&#xff1a;Apple M1 MacOS Sonoma 14.1.1 软件&#xff1a;Android Studio Giraffe | 2022.3.1 Patch 3 设备&#xff1a;小米10 Android 13 一、创建测试项目 安卓 HelloWorld 项目: 安卓 HelloWorld 项目 二、数据线连接手机 1. 手机开启开发者模式 参考&#xff1…

FFmpeg之将视频转为16:9(横屏)或9:16(竖屏)(一)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

代码随想录算法训练营第一天 | 704. 二分查找 27. 移除元素

class Solution { public:int search(vector<int>& nums, int target) {int l0;int rnums.size()-1;while(l<r){int mid(lr)>>1;if(targetnums[mid]) return mid;if(target>nums[mid]){lmid1;}else{rmid-1;}}return -1;} }; 之前就已经熟悉二分法了&am…

【HuggingFace Transformer库学习笔记】基础组件学习:pipeline

一、Transformer基础知识 pip install transformers datasets evaluate peft accelerate gradio optimum sentencepiece pip install jupyterlab scikit-learn pandas matplotlib tensorboard nltk rouge在host文件里添加途中信息&#xff0c;可以避免运行代码下载模型时候报错…