Redian新闻
>
[合集] 解一道 GOOGLE 面试题 ... (转载)
avatar
[合集] 解一道 GOOGLE 面试题 ... (转载)# Programming - 葵花宝典
c*d
1
☆─────────────────────────────────────☆
observer (笑看人生) 于 (Tue Jun 19 20:27:17 2007) 提到:
题目:
求直方图的最大内接矩形,假设每个细条的宽度为1
好象还没见着解法,我来抛砖引玉吧.
就是找2点x1 < x2, 对应高度h(x), x in [a, b]
S = (x2 - x1)*min h(x), x in [x1, x2]
求 max S
直观解法是列举x1, x2, O(N^2)
先看几个简单情况,细条高度如果是连续值:
1. 单调递减
x1=a, x2 in (a, b]
遍历细条找max area的内接矩形 O(N)
2. 单调递增
和1类似,x1 in [a, b), x2 = b,
遍历, O(N)
3. U 形
分解出 Case 1 和 Case 2,求max
还有 case x1 = a, x2 =b
取3者 max, O(N)
4. n 形
如果2端的细条高度不一样,还可以分解出Case 1 或 2
x1, x2 分别在 上升坡 和下降坡, 而且高度相等
可以从最高细条
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。