【C# 每日一题9】求最大的矩形
- C# code
DescriptionA 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:[img=http://hi.csdn.net/attachment/201106/1/1376742_1306892143sZcG.gif][/img]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.InputThe 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.OutputFor 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 Input7 2 1 4 5 1 3 34 1000 1000 1000 10000Sample Output84000
解释一下：
输入为：7 2 1 4 5 1 3 3
的时候表示，后面有7个数字，每个数字m代表宽度为1，高度为m的矩形，之后他们都挨着，这样呢，我们需要从中间找出最大的一个矩形结构（可以跨越多个矩形，这个看图大家就理解了）！
输出找到的矩形的面积8
8来自于第三个和第四个矩形，他们两个组成了宽度为2，高度为4的矩形，面积为8
大家想想有什么好办法么？
硬算肯定是可以解决问题，但是好像效率上有点问题，也欢迎大家贴一下代码，练练手啊！！
[解决办法]
说说思路：循环后面七个数，比对旁边的数，大于或者对于自己则继续比对下去，一圈之后再比较各个结果。
[解决办法]
- C# code
static void Main(string[] args) { string s = "7 2 1 5 5 1 3 3"; int[] nums= s.Split(' ').ToList().ConvertAll<int>(x => int.Parse(x)).ToArray(); int[] rects = (int[])nums.Clone(); int max = 0; for (int i = 0; i < nums.Length; i++) { for (int j = i + 1; j < nums.Length; j++) { if (rects[i] > max) max = rects[i]; if (nums[i] > nums[j]) nums[i] = nums[j]; rects[i] = nums[i] * (j-i + 1); } } if (rects.Max() > max) max = rects.Max(); Console.Write(max); Console.Read(); }
[解决办法]
各个矩形的宽度都是1，只是高度不同，是吗？
稍微想了一下，还没有思路。
[解决办法]
写错了一行
- C# code
static void Main(string[] args) { string s = "7 2 1 5 5 1 3 3"; int[] nums= s.Split(' ').ToList().ConvertAll<int>(x => int.Parse(x)).ToArray(); int[] rects = (int[])nums.Clone(); int max = 0; for (int i = 0; i < nums.Length; i++) { for (int j = i + 1; j < nums.Length; j++) { if (nums[i] > nums[j]) nums[i] = nums[j]; rects[i] = nums[i] * (j-i + 1); if (rects[i] > max) max = rects[i]; } } Console.Write(max); Console.Read(); }
------解决方案--------------------
n*log(n)应该可以，简单的话用最小堆可以做。
复杂一点用最小堆 + Rmq也可以做
[解决办法]
[解决办法]
- C# code
int[] list = new int[] { 1, 8, 5, 9, 14, 2, 6, 7, 4, 11, 12, 3, 13 }; int[] bak = new int[list.Length]; Array.Copy(list,bak,bak.Length);//拷贝一份 Array.Sort<int>(bak);//排序 int min, count,temp,res=0; //遍历一遍 for (int i = 0; i < list.Length; i++) { count = 0; min = bak[i]; for (int j = 0; j < list.Length; j++) { if (list[j] < min) { temp = count * min; if (res < temp) { res = temp; } count = 0; } else { count++; } } } Console.WriteLine(res);
[解决办法]
贴的是脚本语言：
private var testArr:ArrayCollection=new ArrayCollection([2, 1, 4, 5, 1, 3, 3]);
protected function button8_clickHandler(event:MouseEvent):void //
{
var length:int=testArr.length;
for (var i:int=0; i < length; i++)
{
var item:int=testArr[i];
var count:int=getMaxWidth(item, testArr);
trace(count*item);
}
}
private function getMaxWidth(n:int, arr:ArrayCollection):int
{
var count:int=1;
var index:int=arr.getItemIndex(n);
var temp:int;
if (index > 0)
for (var i:int=index - 1; i >= 0; i--)
{
temp=int(arr[i]);
if (temp < n)
{
break;
}
count++;
}
if (index < arr.length - 2)
for (var j:int=index + 1; j < arr.length - 1; j++)
{
temp=int(arr[j]);
if (temp < n)
{
break;
}
count++;
}
return count;
}
打印输出：
2000
6000
8000
5000
6000
3000
3000
[解决办法]
编程思想很重要 不能只为完成工作而工作 那样将是程序员的悲剧!
编程是快乐的, 思想是向上的. 只有本着这样的想法去编程, 生活才会更美好, 代码才会更优美..
只花了10分钟写的代码竟然是所有答案里最优的... 我也很无奈..
希望大家仔细看看自己的代码. 思想是什么?
[解决办法]
[解决办法]
[解决办法]
- C# code
static void Main(string[] args) { int[] numbers = new int[] { 7, 9, 9, 5, 7, 4, 3, 3 }; int max = 0; int temp = 0; for (int i = 0; i < numbers.Length; i++) { for (int j = i + 1; j < numbers.Length; j++) { if (max < numbers[i]) max = numbers[i]; if (numbers[i] > numbers[j]) numbers[i] = numbers[j]; temp = numbers[i] * (j - i + 1); if (temp > max) max = temp; } } Console.Write(max); } }
[解决办法]
- C# code
static void Main(string[] args) { int[] a = { 1, 7, 4, 5, 6, 4, 3, 2, 8, 4, 2, 4, 5 }; int length = 13; int maxHeight = GetMaxHeight(a, length); int maxArea = 0; for (int i = 1; i < maxHeight + 1; i++) { if (maxArea < i * GetMaxWidth(a, length, i)) { maxArea = i * GetMaxWidth(a, length, i); } } Console.WriteLine(maxArea.ToString()); } static int GetMaxWidth(int[] a, int length, int height) { int MaxWidth = 0; int width = -1; for (int i = 0; i < length; i++ ) { if (a[i] < height) { width = -1; } else { width++; if (MaxWidth < width) { MaxWidth = width; } } } return MaxWidth; } static int GetMaxHeight(int[] a, int length) { int max = 0; for (int i = 0; i < length; i++) { if (max < a[i]) { max = a[i]; } } return max; }
[解决办法]
[解决办法]
[解决办法]
哦，用简单的方法更有效，比线段树、最小堆、二叉搜索树都更高效，这个是O(n)的。