代码随想录训练营Day 63|力扣42. 接雨水、84.柱状图中最大的矩形

本文主要是介绍代码随想录训练营Day 63|力扣42. 接雨水、84.柱状图中最大的矩形,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.接雨水

代码随想录

代码:(单调栈)

class Solution {
public:int trap(vector<int>& height) {int result = 0;stack<int> st;st.push(0);for(int i = 1; i < height.size(); i++){if(height[i] < height[st.top()]){st.push(i);}else if(height[i] == height[st.top()]){st.pop(); // 元素值相等留一个就好了,避免重复计算。不过这句话删了也可以st.push(i);}else{while(!st.empty() && height[i] > height[st.top()]){int mid = st.top();st.pop(); // 这里有了pop操作就要注意让栈不为空时再操作if(!st.empty()){int h = min(height[i],height[st.top()]) - height[mid];int w = i - st.top() - 1;result += h * w;}}st.push(i);}}return result;}
};

思路:(这里是横着求矩形面积的)

其实就是找每个元素前面第一个比它大的值(就是单调栈里的栈顶元素的下一个值),和后面第一个比它大的值(用单调栈,第一次比栈顶元素大的当前遍历的元素值)。

矩形的高=这两个值高度的最小值-当前计算的元素高度

矩形的宽=后面元素下标值-前面元素的下标值-1

注意:单调栈里存的都是下标。

2.柱状图中最大的矩形

 代码随想录

代码: (单调栈)

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;stack<int> st;heights.insert(heights.begin(),0);heights.push_back(0);// 向数组首位位置加0,为了避免 因为数组本身就单调 而出现 没有走到计算面积的步骤st.push(0);for(int i = 1; i < heights.size(); i++){if(heights[i] > heights[st.top()]){st.push(i);}else if(heights[i] == heights[st.top()]){st.pop();st.push(i);}else{while(!st.empty() && heights[i] < heights[st.top()]){int h = heights[st.top()];st.pop();if(!st.empty()){int w = i - st.top() - 1;int sum = w * h;result = max(result,sum);}}st.push(i);}}return result;}
};

思路:

和接雨水的区别就是,这里用的是递减栈,以及需要在数组首末补0

基于每一个高度,求左右两边最邻近的比它高度小的元素。

矩形的高=当前计算的元素高度

矩形的宽=后面元素下标值-前面元素的下标值-1

首先来说末尾为什么要加元素0?

如果数组本身就是升序的,例如[2,4,6,8],那么入栈之后 都是单调递减,一直都没有走 情况三 计算结果的哪一步,所以最后输出的就是0了。

开头为什么要加元素0?

如果数组本身是降序的,例如 [8,6,4,2],在 8 入栈后,6 开始与8 进行比较,此时我们得到 mid(8),rigt(6),但是得不到 left。

(mid、left,right 都是对应版本一里的逻辑)

因为 将 8 弹出之后,栈里没有元素了,那么为了避免空栈取值,直接跳过了计算结果的逻辑。

之后又将6 加入栈(此时8已经弹出了),然后 就是 4 与 栈口元素 8 进行比较,周而复始,那么计算的最后结果resutl就是0

这篇关于代码随想录训练营Day 63|力扣42. 接雨水、84.柱状图中最大的矩形的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1079383

相关文章

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部