c***d
发帖数: 996 | 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 分别在 上升坡 和下降坡， 而且高度相等
可以从最高细条 |
|
