最大矩形面积leetcode_leetcode免费吗

最大矩形面积leetcode_leetcode免费吗原题链接给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。示例:输入: [2,1,5,6,2,3]输出: 10题解对于每一个长方体,找出左边比他小的第一个长方体和右边比他小的第一个长方体,然后遍历求结即可class Solution {public

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接

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

求在该柱状图中,能够勾勒出来的矩形的最大面积。
在这里插入图片描述
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。
在这里插入图片描述
图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

题解
对于每一个长方体,找出左边比他小的第一个长方体和右边比他小的第一个长方体,然后遍历求结即可

class Solution { 

public:
int largestRectangleArea(vector<int>& heights) { 

vector<int>left,right;
stack<int>stk;
for(int i = 0;i < heights.size();i ++){ 

while(!stk.empty() && heights[stk.top()] >= heights[i])stk.pop();
if(stk.empty())left.push_back(-1);
else left.push_back(stk.top());
stk.push(i);
}
while(!stk.empty())stk.pop();
for(int i = heights.size() - 1;i >= 0;i --){ 

while(!stk.empty() && heights[stk.top()] >= heights[i])stk.pop();
if(stk.empty())right.push_back(heights.size());
else right.push_back(stk.top());
stk.push(i);
}
reverse(right.begin(),right.end());
int res = 0;
for(int i = 0;i < heights.size();i ++){ 

res = max(res, heights[i] * (right[i] - left[i] - 1));
}
return res;
}
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168746.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Unity Cinemachine插件全功能详解

    Unity Cinemachine插件全功能详解实现电影级别的分镜,推拉式镜头等,需要2017以上的版本才能使用,配合TimeLine一起使用,和Animator一起.虚拟摄像机不支持AlignwithView【有BUG】还是手动拖比较好1:实现简单的相机跟随效果使用TimeLine实现,由于这次不同于“Unity动画系统案例1”那样需要对人物进行控制。这个项目只是单纯的做CG效果。所以不需要指定动画状态机【但必须挂在Animator…

  • java下载文件或文件夹

    java下载文件或文件夹最近接到一个需求,就是将远程目录下的文件或文件夹下载到指定目录下,下面来看下最后的成果。1.首先,IO流输出文件(可以在浏览器端下载)publicHttpServletResponsedownload(StringfileName,HttpServletResponseresponse){Filefile=newFile(gitConfig.getDestPath()+”/”+fileName);if(file.isDirec

  • 汇编语言中各种移位指令的区别与联系

    汇编语言中各种移位指令的区别与联系本文转载自:https://blog.csdn.net/richerg85/article/details/27558005SHL、SHR、SAL、SAR:移位指令;SHL(ShiftLeft):   逻辑左移;SHR(ShiftRight):   逻辑右移;SAL(ShiftArithmeticLeft):算术左移;SAR(Shift…

  • SSRF漏洞挖掘的思路与技巧

    SSRF漏洞挖掘的思路与技巧

  • 2021.9 idea MyBatis Log Plugin 激活码(JetBrains全家桶)

    (2021.9 idea MyBatis Log Plugin 激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • python pandas fillna_pandas删除行

    python pandas fillna_pandas删除行DataFrame.fillna(self,value=None,method=None,axis=None,inplace=False,limit=None,downcast=None,**kwargs)使用指定的方法填充NA/NaN值。参数:value:scalar(标量),dict,Series,或DataFrame用于填充孔的值(例如0),或者是dict/Seri…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号