Today is A good day!心情大好,所以连发博客,记录一下自己苦苦鏖战准备CCF的血泪史ᕙ[・・]ᕗ好,这篇是官网模拟题的第三题,最大的矩形
这个解决起来还是比较棘手的。关键在于怎么样才能获取到最大的那个矩形==。为了这个,我也是纠结了老半天,最后没办法只好看看网上大神怎么说。最后在结合了几篇博文的深入骨髓的洗礼之后,偶终于懂得了这道题的精华所在,特此记录下来。这个算法的思路是这样的,也算是一种穷举算法(但穷举之外还隐含着分治的思想)吧:以某个矩形为基础,分两个方向(分治)遍历,只要找到比它自己的面积大的矩形就继续遍历,因为这样才能最终得到最大的矩形。如果找到的矩形面积比它自己小,就break;如此以来最后最大的矩形面积就是这个矩形的高 * 遍历的宽度(这个宽度当然是前后两个方向遍历的总宽度width)。 当然对每个矩形都需要做相同的遍历,最后取最大的。
这样子就好啦,把类名改成Main,提交,第三个“100分”到手!!! ♪(´ε`)