Largest Rectangle in a Histogram
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7296Accepted Submission(s): 2037
Problem Description
A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights
2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:
Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned
at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
Input
The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, ..., hn, where 0 <= hi <= 1000000000.
These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.
Output
For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.
Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Sample Output
还有一个类似的题。
动态规划-面积最大的全1子矩阵
关键点都是遍历两次,找到左界限和右界限。
#include <stdio.h>
typedef long long int64;
int64 n;
int64 arr[100002];
int64 left[100002], right[100002];
int main() {
//freopen("input.txt", "r", stdin);
while (scanf("%I64d",&n), n) {
for (int i = 1; i <= n; i++) {
scanf("%I64d",&arr[i]);
}
arr[0]=-1;arr[n+1]=-1;
int64 tmp;
for (int i = 1; i <= n; i++) { //求左界限
tmp = i;
while(arr[i] <= arr[tmp-1]) {
tmp = left[tmp-1];
}
left[i] = tmp;
}
int64 ans = 0,max;
for(int i=n; i>=1; i--) { //求右界限,同时求最大值
tmp=i;//
while(arr[i] <= arr[tmp+1]) {
tmp = right[tmp+1];
}
right[i] = tmp;
max = (tmp-left[i] + 1) * arr[i];
if(max > ans)
ans = max;
}
printf("%I64d\n",ans);
}
return 0;
}
分享到:
相关推荐
LeetCode题目Largest Rectangle in Histogram 解答
LintCode - 122. Largest Rectangle in Histogram(直方图最大矩形覆盖)(单调栈)题目链接题目解析主要是运用单调栈(单
http://blog.csdn.net/two_water/article/details/53004027 LeetCode_直方图最大面积(Largest Rectangle in Histogram)
力扣最大面积直方图中最大的矩形 给定 n 个非负整数表示直方图的条形高度,其中每个条形的宽度为 1,求直方图中最大矩形的面积。 上面是一个直方图,其中每个条的宽度为 1,给定高度 = [2,1,5,6,2,3]。...
npm install --save @mapbox/mapbox-gl-draw mapbox-gl-draw-rectangle-restrict-area 用法 import MapboxDraw from "@mapbox/mapbox-gl-draw" ; import DrawRectangle , { DrawStyles , } from "mapbox-gl-draw-...
XNA Tutorial Collision Series 1 - 2D Rectangle Collision
npm install check-point-in-rectangle 用法 var checkPointIn = require ( 'check-point-in-rectangle' ) ; checkPointIn ( point , rectangle [ , precision ] ) x 和 y 坐标点数组四个角点的矩形数组算法中...
C#-矩形-Rectangle
In this paper, we examine the security of reduced AES-192 and AES-256 against related-key rectangle attacks by exploiting the weakness in the AES key schedule. We find the following two new attacks: 9...
对18轮SMS4的改进矩形攻击,孔祥龙,王薇,SMS4是一个32轮的加密算法,它的分组长度和密钥长度都为128比特。SMS4应用于WAPI,中国的无线局域网国家标准。在这篇论文中,本文分析了SMS4
draw-rectangle-and-circle.zip
RectangleGridLayout is a container that arranges views into a gird of rectangles of the same sized. Note, this is NOT a meant to be replaced GridView or TableLayout/GridLayout, rather it's a much ...
A new method based on Maxwell's equations, ABCD ray matrices, and total internal reflection is proposed to theoretically analyze the characteristics of eigenmodes confined in nano-width rectangle ...
The tunable multiple plasmon-induced transparency (PIT) effect is investigated numerically in a metal-insulator-metal (MIM) waveguide with three side-coupled rectangular resonators. The system ...
Implement-an-Interface-to-Change-Rectangle-Dimensions
largest-rectangle-in-histogram: 最长递增子序列: 最长公共自序列: Something about: best time to buy and sell stack: 单链表中的环,两个单链表的公共点。 populating-next-right-pointers-in-each-node-ii: ...
GeoJSON的最小边界矩形 此Javascript / Typescript库提供了两种方法,...yarn add geojson-minimum-bounding-rectangle 或者 npm install geojson-minimum-bounding-rectangle 用法 import { smallestSurroundingRec
商业编程-源码-Csharp实例18 rectangle.zip
matlab说话代码检测医学图像中的矩形标记 使用形态学开放和霍夫变换检测医学图像中的白色矩形标记。 中文版自述文件,见。 内容 背景 医学图像通常具有医生标记的感兴趣区域。 一般而言,在构建深度学习模型之前,...
在打开此页面 用作扩展 该存储库可以作为扩展添加到MakeCode中。 打开 ...搜索并导入 编辑这个专案 要在MakeCode中编辑此存储库。... 单击导入,然后单击导入URL ...此图显示了master中最后一次提交的块代码。...