j***n
发帖数: 301 | 1 有道题目最近频繁出现，特地总结一下常规解法以及它的变体。有个经典变体我还没看
到一个很经典的答案，希望有人补上，呵呵。
1. The largest rectangle under a histogram
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
Given: An integer array represents a histogram
Goal: Find the largest rectangle under the histogram.
Key observation: 输入为一个整数数组。如果某元素比它两边的邻居都小（比如Ai)，
那么高度大于Ai的矩阵要么在该元素左边，要么在该元素右边，不可能穿过Ai。利用这
个性质，想办法遍历所有的矩形。
Complexity O(N) where N is the size of the given array.
2. Maximum subarray with all 1’s. (Generalization of problem 1)
http: |
b******v
发帖数: 1493 | 2 great! thanks
【在 j***n 的大作中提到】
: 有道题目最近频繁出现，特地总结一下常规解法以及它的变体。有个经典变体我还没看
: 到一个很经典的答案，希望有人补上，呵呵。
: 1. The largest rectangle under a histogram
: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
: Given: An integer array represents a histogram
: Goal: Find the largest rectangle under the histogram.
: Key observation: 输入为一个整数数组。如果某元素比它两边的邻居都小（比如Ai)，
: 那么高度大于Ai的矩阵要么在该元素左边，要么在该元素右边，不可能穿过Ai。利用这
: 个性质，想办法遍历所有的矩形。
: Complexity O(N) where N is the size of the given array.
|
c********t
发帖数: 1756 | |
l******4
发帖数: 207 | 4 shou cang
【在 j***n 的大作中提到】
: 有道题目最近频繁出现，特地总结一下常规解法以及它的变体。有个经典变体我还没看
: 到一个很经典的答案，希望有人补上，呵呵。
: 1. The largest rectangle under a histogram
: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
: Given: An integer array represents a histogram
: Goal: Find the largest rectangle under the histogram.
: Key observation: 输入为一个整数数组。如果某元素比它两边的邻居都小（比如Ai)，
: 那么高度大于Ai的矩阵要么在该元素左边，要么在该元素右边，不可能穿过Ai。利用这
: 个性质，想办法遍历所有的矩形。
: Complexity O(N) where N is the size of the given array.
|
w****l
发帖数: 88 | |
j***n
发帖数: 301 | 6 谁来说说这个题的思路？
4. Imagine you have a square matrix, where each cell is filled with either b
lack or white. Design an algorithm to find the maximum subsquare such that a
ll four borders are filled with black pixels. (variation of problem 3)
http://careercup.com/question?id=2445
??? |
r****o
发帖数: 1950 | 7 谢谢你的总结。
能不能说下第2题的直方图是怎么构建的啊？多谢。
b
a
【在 j***n 的大作中提到】
: 谁来说说这个题的思路？
: 4. Imagine you have a square matrix, where each cell is filled with either b
: lack or white. Design an algorithm to find the maximum subsquare such that a
: ll four borders are filled with black pixels. (variation of problem 3)
: http://careercup.com/question?id=2445
: ???
|
j***n
发帖数: 301 | 8 那个链接里面有，只是没叫直方图而已。我现在把那段代码截取注释一下。
输入是一个二维矩阵b，M行N列。
所谓的cache，也就是直方图，存在一个一维数组c里
c[0 .. M-1] = 0
main algorithm:
for x = N-1 .. 0 //从右向左扫描每一列
update_cache(x) //构造直方图
// 对c做直方图算法，找最大矩阵。
end main algorithm
define update_cache(x)
for y = 0 .. M-1
if b[x, y]!=0
c[y] = c[y]+1
else
c[y] = 0
【在 r****o 的大作中提到】
: 谢谢你的总结。
: 能不能说下第2题的直方图是怎么构建的啊？多谢。
:
: b
: a
|
m*****g
发帖数: 226 | 9 可以用那个D博士的遍历办法，预处理，然后检查每个可能的方块。O(n3)
b
a
【在 j***n 的大作中提到】
: 谁来说说这个题的思路？
: 4. Imagine you have a square matrix, where each cell is filled with either b
: lack or white. Design an algorithm to find the maximum subsquare such that a
: ll four borders are filled with black pixels. (variation of problem 3)
: http://careercup.com/question?id=2445
: ???
|
m*****g
发帖数: 226 | |
|
|
m*****g
发帖数: 226 | |
m*****g
发帖数: 226 | 12 dobbs上面最后一题有笔误
一开始的c[0 .. M-1] = 0
应为c[0 .. M] =0 |
j**l
发帖数: 2911 | 13 有笔误，x代表列，y代表行,所以应该是b[y, x]而不是b[x, y]
c[0 .. M-1] = 0
main algorithm:
for x = N-1 .. 0 //从右向左扫描每一列
update_cache(x) //构造直方图
// 对c做直方图算法，找最大矩阵。
end main algorithm
define update_cache(x)
for y = 0 .. M-1
if b[y, x]!=0
c[y] = c[y]+1
else
c[y] = 0 |
b***u
发帖数: 61 | 14 第4题 如果只是要求四个顶点是黑的 应该怎么做呢？ |
m*****g
发帖数: 226 | 15 硬来
【在 b***u 的大作中提到】
: 第4题 如果只是要求四个顶点是黑的 应该怎么做呢？
|
