LeetCode 84.柱状图中最大矩形的面积

Stella981
• 阅读 471

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

求在该柱状图中,能够勾勒出来的矩形的最大面积。

LeetCode 84.柱状图中最大矩形的面积

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]

LeetCode 84.柱状图中最大矩形的面积

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10算法:单调栈。此题是利用栈来解决问题最经典的题目之一。我们可以观察得出,矩形所围成的最大面积取决于它左边跟右边第一个小的矩形的长,为此我们可以维护一个单调栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size(),ans=0;
        heights.push_back(-1);
        stack<int>stk;
        for(int i=0;i<=n;i++){
            while(!stk.empty()&&heights[i]<heights[stk.top()]){
                int cur=stk.top();
                stk.pop();
                if(stk.empty())
                    ans=max(ans,heights[cur]*i);
                else
                    ans=max(ans,heights[cur]*(i-stk.top()-1));
            }
            stk.push(i);
        }
        return ans;
    }
};
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Python使用Plotly绘图工具,绘制柱状图
使用Plotly绘制基本的柱状图,需要用到的函数是graph\_objs中Bar函数通过参数,可以设置柱状图的样式。通过barmod进行设置可以绘制出不同类型的柱状图出来。我们先来实现一个简单的柱状图:coding:utf8importplotlyaspyimportplotly
Stella981 Stella981
3年前
Pyhon数据分析20——matplotlib可视化(二)之柱状图
atplotlib绘制柱状图柱状图(barchart),是一种以长方形的长度为变量的表达图形的统计报告图,由一系列高度不等的纵向条纹表示数据分布的情况,用来比较两个或以上的价值(不同时间或者不同条件),只有一个变量,通常利用于较小的数据集分析。柱状图亦可横向排列,或用多维方式表达。准备importnumpyasnpimport
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Stella981 Stella981
3年前
Leetcode 363.矩形区域不超过k的最大数值和
矩形区域不超过k的最大数值和给定一个非空二维矩阵 _matrix_和一个整数_k_,找到这个矩阵内部不大于_k_的最大矩形和。示例:输入:matrix\\1,0,1\,\0,2,3\\,k2输出:2解释: 矩形区域 \\0,1\,
Stella981 Stella981
3年前
LeetCode 42. 接雨水
给定 _n_ 个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。!(https://oscimg.oschina.net/oscnet/b0cc4f8b9a129e159dc6141c019d5b3c043.png)上面是由数组\0,1,0,2,1,0,1,3,2,1,2,1\表示的高度图,在这种情况
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这