给定直方图,每一小块的height由N个非负整数所确定,每一小块的width都为1,请找出直方图中面积最大的矩形。 如下图所示,直方图中每一块的宽度都是1,每一块给定的高度分别是[2,1,5,6,2,3]; 那么上述直方图中,面积最大的矩形面积 = 10单位。
请完成函数largestRectangleArea,实现寻找直方图中面积最大的矩形的功能,如当给定直方图各小块的高度= [2,1,5,6,2,3] ,返回10。
这一题同样也是英雄会中的题目,难度2星,判为容易一类,不过确实还好;
以每个矩形的高度为基点,左右不断扩散(直到左右的高度低于基点为止)
for(i = 0; i < n; i++) { width = 1; for(front = i - 1; front >= 0; front--) //向前扩增 { if(height[front] >= height[i]) width++; else break; } for(back = i + 1; back < n; back++) //向后扩增 { if(height[back] >= height[i]) width++; else break; } currentArea = width * height[i]; if(LargestArea < currentArea) LargestArea = currentArea; }
如上所示,back = i + 1,front = i - 1;向两边扩增,而width自增;
计算面积 currentArea = height[i] * width;
最后得到最大面积LargestArea;
(我想以每一个点为基点大家没异议吧...无论结果是多少,height肯定是矩形数组的其中一个值,这个大家可以想想,以大家聪明的头脑肯定没问题)
附代码如下:
#include <stdio.h> int largestRectangleArea(const int *height,int n) { int LargestArea = 0, currentArea = 0; //目前最大面积,当前面积 int width; //矩形宽度 int back; //向前扩增 int front; //向后扩增 int i = 0; for(i = 0; i < n; i++) { width = 1; for(front = i - 1; front >= 0; front--) //向前扩增 { if(height[front] >= height[i]) width++; else break; } for(back = i + 1; back < n; back++) //向后扩增 { if(height[back] >= height[i]) width++; else break; } currentArea = width * height[i]; if(LargestArea < currentArea) LargestArea = currentArea; } return LargestArea; } int main() { int rect[] ={2, 1, 5, 6, 2, 3}; int n = sizeof(rect) / sizeof(int); int LargestArea = largestRectangleArea(rect, n); int i; for(i = 0; i < n - 1; i++) { printf("%d, ", rect[i]); } printf("%d", rect[i]); printf("\n%d\n", LargestArea); return 0; }