leetcode Largest Rectangle in Histogram || leetcode Maximal Rectangle

本次题解包括

  • 84. Largest Rectangle in Histogram
  • 85. Maximal Rectangle

84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

题目地址:leetcode Largest Rectangle in Histogram

题目大意:给定数组height表示矩形的高度,求矩形围城的矩形区域最大面积。

思路:很容易想到O(n^2)方法,枚举起始,枚举结束。。。用栈的话可以有O(N)的方法。

用一个栈来维护一个递增序列的下标:

  1. 如果当前的高度不大于栈顶的元素高度,那么pop并更新直到比当前元素的高度小的时候。更新的时候需要注意的是,用栈顶的高度作为计算的高(这样做的原因是栈顶的高一定比到当前下标i之间的元素来的小,这样就相当于有了起点和终点,这个区间可以采用当前栈顶的高)所以宽度为i – 1 – q.top() (i不计算在内,故-1,)当q为空时候,说明当前高度是“有史以来”最小的,宽度应该为i。
  2. 否则把当前下标入栈。
  3. 当全部元素都过完一遍,但是栈不为空的时候,可以想象为height[n]==int_min的时候,按第一步进行更新。

C++

 

Python

 

 


 

85. Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

题目地址:leetcode Maximal Rectangle

题目大意:给定由0和1组成的矩阵,求由1构成的最大矩阵。如:

0110

1010为2.

思路:设dp[i][j]为(i,j)这列上连续1的个数,然后就相当于求给定矩形高度,求最大矩形面积。。

你就秒懂之一图流:

(到最后一行可以转化为给定高度为:0,1,2,3的矩形, 求其最大矩形面积)

QQ截图20150226231110

就是上面那一题。

leetcode两题放一起真是用心良苦。。

C++

 

Python

 

本文是leetcode如下的题解

  • 84. Largest Rectangle in Histogram
  • 85. Maximal Rectangle

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Largest Rectangle in Histogram || leetcode Maximal Rectangle
本文地址:https://www.hrwhisper.me/leetcode-largest-rectangle-in-histogram-and-leercode-maximal-rectangle/

打赏一杯咖啡钱呗

Leetcode . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *