379,柱状图中最大的矩形(难) |
您所在的位置:网站首页 › 柱状图中的最大矩形 › 379,柱状图中最大的矩形(难) |
Remember, quitters never win...and winners never quit. 记住,放弃者难以成功,成功者决不放弃。 问题描述 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。 图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3] 输出: 10 问题分析 01暴力求解最简单的方式就是暴力求解,我们都知道暴力求解的效率很差,但不妨碍我们做出来。暴力求解有两种方式。
一种是从左边确定一根柱子,然后从左往右扫描,确定以当前柱子的高为最大高度所围成的最大矩形(这个矩形的高度不能超过当前柱子的高度),记录下最大面积。
还一种是确定一根柱子以后分别从他的前后两个方向扫描,确定以当前柱子高度为矩形的高所围成的最大矩形(这个矩形的高度就是当前这个柱子的高度),记录下最大面积。
我们来分别看下这两种写法的代码 1public int largestRectangleArea(int[] heights) { 2 int length = heights.length; 3 int area = 0; 4 // 枚举左边界 5 for (int left = 0; left = 0; i--) {22 int p = i + 1;23 while (p = height[i]) {24 p = rightLess[p];25 }26 rightLess[i] = p;27 }28 int maxArea = 0;29 //以每个柱子的高度为矩形的高,计算矩形的面积。30 for (int i = 0; i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |