天涯不让发。。。英美中感受 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

天涯不让发。。。英美中感受 (转载)

天涯不让发。。。英美中感受 (转载)# Joke - 肚皮舞运动

c*e2010-07-30 07:07

1 楼

1. How to find the maximum rectangular in a histogram. You have the heights
of the histogram H[i], i=1,...,N.
2. Give a matrix x[i][j], i,j=1,...,N, which contain 0, 1 only. How to find
the maximum rectangular which contain 0 only.

z*n2010-07-30 07:07

2 楼

【以下文字转载自 WaterWorld 讨论区】
发信人: yy198709 (yy198709), 信区: WaterWorld
标题: 天涯不让发。。。英美中感受
发信站: BBS 未名空间站 (Fri Jul 30 12:07:24 2010, 美东)
这就是英国来源：包子
加补充，这就是美国和中国来源：小猪
我来英国马上快两年了，我给大家讲讲英国的样子：包子
我来美国马上快5年了，补充讲讲美国的样子：小猪
我们都在中国出生长大度过了20多年
我们都希望祖国真的脚踏实地的好起来
英国并不是大家想象的到处是灯红酒绿、遍地黄金的大都市，有时候你甚至觉得这是农
村。之所以他是发达国家，是因为英国稳定的社会秩序，和谐的社会情绪（不是政府
的强制干预而和谐）。如果把一个国家比作一辆车，这真的是一部运行优良的跑车。
美国，很多美国本地人都不喜欢NY的繁华一并脏乱
中国，争抢着建立国际化都市，同步鄙视着自己的同胞
衣着要名牌，车子要高档，房子要豪华，仿佛这样就高于别人一等，心里才能安慰
在英国，你做很多事情都需要打电话预定，比如你去剪头发，去看医生。
在美国，同样
在中国，走后

A*r2010-07-30 07:07

3 楼

都是DP.
第一个很简单，对每一个高度，分别记录能够到达的最左和最右的坐标，最后最大的那个就是。。
Let L(i)=R(i)=i at first, then
更新 L(i)=L(i-1) while H[i]<=H[j] j=i-1..0
更新 R(i)=R(i+1) while H[i]<=H[j] j=i+1..n
最后max { H[i]*(R(i)-L(i)) } 就是最大的矩形。这个算法不是最优的。。
第二个比较复杂，brute force 估计要用O(n^3), 最好貌似可以做到O(n^2).
参见 http://www.drdobbs.com/184410529

heights
find

【在 c**********e 的大作中提到】

: 1. How to find the maximum rectangular in a histogram. You have the heights
: of the histogram H[i], i=1,...,N.
: 2. Give a matrix x[i][j], i,j=1,...,N, which contain 0, 1 only. How to find
: the maximum rectangular which contain 0 only.

a*92010-07-30 07:07

4 楼

"街头没有乞丐,只有幸福的街头艺人"
请问怎样才能穿越到帖子当中的这个美国去?

【在 z**n 的大作中提到】

: 【以下文字转载自 WaterWorld 讨论区】
: 发信人: yy198709 (yy198709), 信区: WaterWorld
: 标题: 天涯不让发。。。英美中感受
: 发信站: BBS 未名空间站 (Fri Jul 30 12:07:24 2010, 美东)
: 这就是英国来源：包子
: 加补充，这就是美国和中国来源：小猪
: 我来英国马上快两年了，我给大家讲讲英国的样子：包子
: 我来美国马上快5年了，补充讲讲美国的样子：小猪
: 我们都在中国出生长大度过了20多年
: 我们都希望祖国真的脚踏实地的好起来

c*l2010-07-30 07:07

5 楼

=> what does it mean by maximum here? the length or the area? thanks

【在 A*********r 的大作中提到】

: 都是DP.
: 第一个很简单，对每一个高度，分别记录能够到达的最左和最右的坐标，最后最大的那个就是。。
: Let L(i)=R(i)=i at first, then
: 更新 L(i)=L(i-1) while H[i]<=H[j] j=i-1..0
: 更新 R(i)=R(i+1) while H[i]<=H[j] j=i+1..n
: 最后max { H[i]*(R(i)-L(i)) } 就是最大的矩形。这个算法不是最优的。。
: 第二个比较复杂，brute force 估计要用O(n^3), 最好貌似可以做到O(n^2).
: 参见 http://www.drdobbs.com/184410529
:
: heights

z*n2010-07-30 07:07

6 楼

这么多的基点，早知道我就拆开搞个连载骗包子,nnd.

A*r2010-07-30 07:07

7 楼

谢谢提醒，应该是面积，忘了乘上H[i]了，已经改了。。

【在 c****l 的大作中提到】

:
: => what does it mean by maximum here? the length or the area? thanks

s*y2010-07-30 07:07

8 楼

Most parts are actually correct. Some minor parts are wrong.

【在 z**n 的大作中提到】

: 这么多的基点，早知道我就拆开搞个连载骗包子,nnd.

h*k2010-07-30 07:07

9 楼

第一题的算法不对。按你这个思路，对于H[i]，你必须比较所有的H[j]和H[i]，来找到
高度为H[i]的矩形的左右边界。这样复杂度是O(n^2)。正确算法是用stack。
第二题的brute force是O(n^6)，最后利用第一题的思路，可以到O(n^2)。

【在 A*********r 的大作中提到】

s*w2010-07-30 07:07

10 楼

说实话，我没看出啥g点，可能认识不是很深刻就是了

【在 z**n 的大作中提到】

: 这么多的基点，早知道我就拆开搞个连载骗包子,nnd.

l*o2010-07-30 07:07

11 楼

1.我用递归做的:
遍历整个数组,找到最小值min,
返回max(min*len,min左边一半数组的最大矩形,min右边一半数组的最大矩形)

heights
find

【在 c**********e 的大作中提到】

x*g2010-07-30 07:07

12 楼

这就是zhuangbility？

l*o2010-07-30 07:07

13 楼

第二道我是这么做的:
对于数组中每一行:
遇到0,则为前面一个加一,遇到1则清零
e.g.0011010->1200101
在得到的二维矩阵里,对每一个数竖着看,算出每个对应的最大值
e.g.
2
3
4
5
->9

heights
find

【在 c**********e 的大作中提到】

a*52010-07-30 07:07

14 楼

有一些说的是实情,但大多不是搞笑就是不知所云,闲的蛋疼,来总结一下吧
搞笑型:
在英国，如果你搞科研需要买一个软件，需要一份详细的论证报告，少则几十页，多则上百页，经过专家和部门认定后才会为你购买。
在英国，你永远可以在你住的方圆500米内找到一个足球场。
在美国，换成了橄榄球场和大大小小的开放式公园
在英国，夜生活是很单调的，大部分英国人去的只有酒吧，少量富人也去赌场。
在美国，去赌场是很寻常的事，多数人就是见识一下，然后走人
在中国，沉迷赌局，各种陷阱，万劫不复了
在英国，工作不努力的人大都人际不太好，因为工作态度无法被认同。
在美国，一样
在英国，你要为你忘记关灯或水龙头而感觉自己可耻，请留一些资源给子孙后代。
在美国，电费很贵的。。。
在中国，在家珍惜，公共挥霍
在英国，如果你受人喜欢，很多英国人很希望跟你学习你的母语。
在美国，一样
在中国，小孩子国语都没掌握，就开始学英文了。。。
在英国，非成年人购买烟酒属于监护人违法。
在美国，一样，查ID
在中国，随便您，大学里喝得烂醉的比比皆是
在英国，很多科学的前提是环保，不是利益。
在美国，环保概念随处可见比如薄了的矿泉水瓶，比如

【在 s*****w 的大作中提到】

: 说实话，我没看出啥g点，可能认识不是很深刻就是了

h*k2010-07-30 07:07

15 楼

worst case O(n^2), if you need O(n) to find a minimum value

【在 l**o 的大作中提到】

: 1.我用递归做的:
: 遍历整个数组,找到最小值min,
: 返回max(min*len,min左边一半数组的最大矩形,min右边一半数组的最大矩形)
:
: heights
: find

l*e2010-07-30 07:07

16 楼

大多数还是属实的！

p*72010-07-30 07:07

17 楼

解法都倒背如流了，从来没遇到有人考....

s*q2010-07-30 07:07

18 楼

大多数在搞笑，原文作者精神外F得已经无药可救了

【在 l*****e 的大作中提到】

: 大多数还是属实的！

A*r2010-07-30 07:07

19 楼

谢谢指正，赶紧回去查了一下前几天看的DP网页, 上面赫然写着O(n)，害我想当然以为
这就是最优解，没有去仔细推导算法复杂度。。唉，还是自己理解不够深刻。。
第二题你能大概说说么？

【在 h**k 的大作中提到】

: 第一题的算法不对。按你这个思路，对于H[i]，你必须比较所有的H[j]和H[i]，来找到
: 高度为H[i]的矩形的左右边界。这样复杂度是O(n^2)。正确算法是用stack。
: 第二题的brute force是O(n^6)，最后利用第一题的思路，可以到O(n^2)。

c*e2010-07-30 07:07

20 楼

Which DP网页?

【在 A*********r 的大作中提到】

: 谢谢指正，赶紧回去查了一下前几天看的DP网页, 上面赫然写着O(n)，害我想当然以为
: 这就是最优解，没有去仔细推导算法复杂度。。唉，还是自己理解不够深刻。。
: 第二题你能大概说说么？