我有一个高度为整数且宽度恒定为1的直方图。我想最大化直方图下面的矩形区域。 例如:
_
| |
| |_
| |
| |_
| |
答案是6,即使用col1和col2相乘得到。
我知道O(n^2)的暴力方法,但我想要一个O(n log n)的算法。我尝试考虑最大递增子序列的动态规划算法(O(n log n)),但是卡住了。我应该使用分治算法吗?
PS:有足够声望的人请删除divide-and-conquer标签,如果没有这样的解决方案。
mho的评论之后:我的意思是适合完全适配的最大矩形区域。(感谢j_random_hacker澄清 :))。