解一道 GOOGLE 面试题 ...# JobHunting - 待字闺中
o*r
1 楼
求直方图的最大内接矩形,假设每个细条的宽度为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 分别在 上升坡 和下降坡， 而且高度相等
可以从最高细条分别从两边找等高细条，h(x1) = h(x2)，找max
O(N)
5. 一般情况
按照 Case 1, 2 分解，发现剩下若干不相邻的 Case 4
依次按 Case 4求解，
还有case
好象还没见着解法，我来抛砖引玉吧.
就是找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 分别在 上升坡 和下降坡， 而且高度相等
可以从最高细条分别从两边找等高细条，h(x1) = h(x2)，找max
O(N)
5. 一般情况
按照 Case 1, 2 分解，发现剩下若干不相邻的 Case 4
依次按 Case 4求解，
还有case