Largest Rectangle in Histogram - 未名空间MITBBS历史存档

Largest Rectangle in Histogram# JobHunting - 待字闺中

p*e2013-09-23 07:09

1 楼

晒晒我贴心儿子的趣事：
1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
楼送“药”给爸爸。
2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有
了。

b*m2013-09-23 07:09

2 楼

没想出用stack方法，我这个也是O(n)吧？
public class Solution {
public int largestRectangleArea(int[] height) {
if(height.length ==0 ){
return 0;
}
int[] left= new int[height.length]; // width on its left side(and
itself)
int[] right= new int[height.length]; // width on its right side(and
itself)

left[0] = 1;
right[right.length-1] = 1;

for(int i=1;i< height.length; i++){
if(height[i]> height[i-1]){
left[i] = 1;
}else if(height[i] == height[i-1]){
left[i] = left[i-1] +1;
}else{
left[i] = 1;
int j = i-1;
while(j>=0 && height[i] <= height[j]){
left[i] += left[j];
j-= left[j]; //jump
}
}
}

for(int i = right.length -2;i>=0;i--){
if(height[i]>height[i+1]){
right[i] = 1;
}else if(height[i] == height[i+1]){
right[i] = right[i+1] +1;
}else{
right[i] = 1;
int j = i+1;
while(j < right.length && height[i] <= height[j]){
right[i] += right[j];
j+= right[j]; //jump
}
}
}

int max = 0;
for(int i=0;iint area = (left[i] + right[i] -1) *height[i];
if(area> max){
max = area;
}
}
return max;
}
}

c*s2013-09-23 07:09

3 楼

nice

b*g2013-09-23 07:09

4 楼

public class Solution {
public int largestRectangleArea(int[] height) {
// Start typing your Java solution below
// DO NOT write main() function
if(height == null || height.length == 0) return 0;
int n = height.length;
int[] left = new int[n];
Stack stack = new Stack();
int max = 0;
for(int i = 0; i < n; i++){
if(stack.empty() || height[stack.peek()] <= height[i]){
left[i] = i;
stack.push(i);
}else{
while(!stack.empty() && height[stack.peek()] > height[i]){
int idx = stack.pop();
left[i] = left[idx];
max = Math.max(max, height[idx] * (i - left[idx]));
}
stack.push(i);
}
}
while(!stack.empty()){
int idx = stack.pop();
max = Math.max(max, height[idx] * (n - left[idx]));
}
return max;
}
}

m*d2013-09-23 07:09

5 楼

第一次听说T家还有1200块的RING卖？

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

: 晒晒我贴心儿子的趣事：
: 1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
: 问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
: 如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
: 楼送“药”给爸爸。
: 2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
: 长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
: 脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
: 时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
: 狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有

s*l2013-09-23 07:09

6 楼

太可爱了吧

y*e2013-09-23 07:09

7 楼

第二个真是心都化掉了

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

: 晒晒我贴心儿子的趣事：
: 1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
: 问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
: 如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
: 楼送“药”给爸爸。
: 2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
: 长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
: 脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
: 时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
: 狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有

y*e2013-09-23 07:09

8 楼

男式婚戒不带钻的1200的足够了

【在 m********d 的大作中提到】

: 第一次听说T家还有1200块的RING卖？

s*y2013-09-23 07:09

9 楼

so sweet! 小人真懂事啊，呵呵

l*o2013-09-23 07:09

10 楼

真是聪明懂事啊～～～～～～～～～～～

p*e2013-09-23 07:09

11 楼

谢谢哈。您真是懂我，当时就是这种感觉。顺带就把他爹原谅啦。:D

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

: 第二个真是心都化掉了

s*32013-09-23 07:09

12 楼

mm是怎么教育的啊，这么贴心的宝贝。看的我都泪汪汪的~~~~~~

n*t2013-09-23 07:09

13 楼

儿子也能这么贴心啊~~~

K*E2013-09-23 07:09

14 楼

这小子好贴心！

s*m2013-09-23 07:09

15 楼

so sweet! :) 你儿子什么星座啊？mm我将来也生一个一样星座的宝贝：）

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

: 晒晒我贴心儿子的趣事：
: 1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
: 问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
: 如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
: 楼送“药”给爸爸。
: 2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
: 长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
: 脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
: 时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
: 狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有

s*m2013-09-23 07:09

16 楼

re！

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

: 第二个真是心都化掉了

k*i2013-09-23 07:09

17 楼

我家2岁的儿子看着电视对他爸爸说：老公，热奶！

p*e2013-09-23 07:09

18 楼

谢谢啊。妹妹有心观察，会发现你的宝宝也一样贴心。其实我觉得他太敏感了。刚刚开
家长会，老师说他爱哭（男孩！！！！）现在好多了，要求家长配合老师让他知道"老
师会make mistakes，妈妈爸爸也会make mistakes, the word is not perfect, but
you don't have to cry":(

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

: mm是怎么教育的啊，这么贴心的宝贝。看的我都泪汪汪的~~~~~~

p*e2013-09-23 07:09

19 楼

哈哈，SO~~~cute.

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

: 我家2岁的儿子看着电视对他爸爸说：老公，热奶！

p*e2013-09-23 07:09

20 楼

狮子座的，祝妹妹好运。：）

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

: so sweet! :) 你儿子什么星座啊？mm我将来也生一个一样星座的宝贝：）

w*32013-09-23 07:09

21 楼

好可爱.....

x*i2013-09-23 07:09

22 楼

哈，你是咋培养出来的，分享一下经验哈~

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

: 晒晒我贴心儿子的趣事：
: 1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
: 问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
: 如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
: 楼送“药”给爸爸。
: 2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
: 长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
: 脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
: 时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
: 狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有

p*y2013-09-23 07:09

23 楼

好贴心！

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

: 晒晒我贴心儿子的趣事：
: 1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
: 问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
: 如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
: 楼送“药”给爸爸。
: 2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
: 长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
: 脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
: 时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
: 狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有

j*a2013-09-23 07:09

24 楼

看你上面写你儿子的事，真是so sweet, so moving。甚至有些难过眼泪就要掉下来了
（我哭点低请
忽略），后面看老师说你儿子的话，我又笑死。真是太可爱啦你儿子。

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

: 谢谢啊。妹妹有心观察，会发现你的宝宝也一样贴心。其实我觉得他太敏感了。刚刚开
: 家长会，老师说他爱哭（男孩！！！！）现在好多了，要求家长配合老师让他知道"老
: 师会make mistakes，妈妈爸爸也会make mistakes, the word is not perfect, but
: you don't have to cry":(

c*62013-09-23 07:09

25 楼

sweet!

W*e2013-09-23 07:09

26 楼

实在太可爱了。
讲一个我两岁儿子的故事：通常他和姐姐一起洗手的时候喜欢玩水，我就“教育”他们
，“不可以玩水，水玩完了鸟鸟和草草喝什么？”通常这一招还是满好使，因为他们喜
欢在有很多大雁的草地上玩。
昨天再这样问时，儿子来了一句：“鸟鸟喝SODA” -前天他爸爸给他和姐姐尝了一些
SODA！！

g*t2013-09-23 07:09

27 楼

真让人钦羡啊,幸福的人儿

p*e2013-09-23 07:09

28 楼

太可爱啦。妹妹的宝宝们都好有仁慈之心。我儿子小时候知道不能喝SODA，因为那是给
爸爸治馋病的药（爸爸天天喝，天天戒）。不知不觉他也知道自己馋要分享点治馋病的
药啦。榜样的力量真是无穷的。

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

: 实在太可爱了。
: 讲一个我两岁儿子的故事：通常他和姐姐一起洗手的时候喜欢玩水，我就“教育”他们
: ，“不可以玩水，水玩完了鸟鸟和草草喝什么？”通常这一招还是满好使，因为他们喜
: 欢在有很多大雁的草地上玩。
: 昨天再这样问时，儿子来了一句：“鸟鸟喝SODA” -前天他爸爸给他和姐姐尝了一些
: SODA！！

p*e2013-09-23 07:09

29 楼

谢谢哈。是啊，儿子的老师们都巨爱他。家长会都是在忍峻不禁的笑声中度过；不过，
对于他的缺点老师还是明察秋毫的，对此我们心中充满感恩。—感恩节有感。

【在 j*****a 的大作中提到】

: 看你上面写你儿子的事，真是so sweet, so moving。甚至有些难过眼泪就要掉下来了
: （我哭点低请
: 忽略），后面看老师说你儿子的话，我又笑死。真是太可爱啦你儿子。

t*n2013-09-23 07:09

30 楼

靠，太贴心了啊

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

: 晒晒我贴心儿子的趣事：
: 1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
: 问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
: 如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
: 楼送“药”给爸爸。
: 2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
: 长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
: 脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
: 时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
: 狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有

O*X2013-09-23 07:09

31 楼

赞，还是要生儿子啊

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

: 晒晒我贴心儿子的趣事：
: 1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
: 问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
: 如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
: 楼送“药”给爸爸。
: 2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
: 长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
: 脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
: 时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
: 狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有

l*t2013-09-23 07:09

32 楼

宝贝这么可人。哈哈

s*m2013-09-23 07:09

33 楼

哇。。。狮子座是我想要的儿子星座排名第一啊！好羡慕：）
替我亲一下你家宝贝，呵呵：）

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

: 狮子座的，祝妹妹好运。：）

p*e2013-09-23 07:09

34 楼

儿子长得又高又壮，皮肤粗糙而黑，说话粗声大气。可是这样一个外表粗枝大叶的男孩
子却时而呈现出极其细腻敏感心。话说当年儿子三岁，我有一段时间工作一天之后很疲
惫，回家的路上便不说话，小人问：妈妈为什么不说话呀？答：累了。小人又问：妈妈
班上好吗？答：好。忽然小人提高噪门大笑，还说mom看我的眼睛怎麼沒了呢。回想起
接他時俺和他老師看孩子們做鬼臉的照片，邊大笑邊說，瞧這個沒眼睛了，那個吐舌頭
啦等等。小人是要鬥媽媽笑呢。俺心頭頓時深感溫暖，如滔滔江水呀。
另有，前天先生說對他說：兒子，爸爸和妈妈决定不买大房子了，这样，不管爸爸是
富翁还是穷人都会送你去最好的中学（私立的）。儿子抱着爸爸的脖子说：谢谢，我愛
你。是流着眼泪呜咽着说的。八岁的小人儿，懂啥呢，感情这麼豐富。這一段是俺發現
兒子心事重重，審問後，老公悄悄交待的。氣得俺明令禁止他們背地裡說這麼沉重悄悄
話。

l*22013-09-23 07:09

35 楼

那个戒指应该留着等孩子结婚的时候给他戴。

t*o2013-09-23 07:09

36 楼

不要把儿子养的这么娘好不好

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

: 晒晒我贴心儿子的趣事：
: 1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
: 问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
: 如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
: 楼送“药”给爸爸。
: 2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
: 长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
: 脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
: 时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
: 狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有

c*n2013-09-23 07:09

37 楼

sweet

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

: 晒晒我贴心儿子的趣事：
: 1-儿子一两岁时，最爱观查各个抽屉，橱柜里的物品。有一次翻出我的女士卫生用品，
: 问这个是什么。我告诉他这是给妈妈治疗肚子痛的，不能随便动。不久，爸爸在卫生间
: 如厕，曰肚子不舒服。小儿迅速下楼翻出Daily Pad。手里举的高高的，咚咚咚咚爬上
: 楼送“药”给爸爸。
: 2-我曾经心血来潮，给老公买了一款tiffany婚戒，约1200。结果节省的老公脸拉的很
: 长很长，说什么男的不能像女的一样，戴什么tiffany，浪费钱，要我退掉。当时偶的
: 脸色也就很不好看，心想“自讨没趣，惊喜变吵架啦。”当儿子的面，啥也没说。儿子
: 时年六岁，抱着偶的腿，眼泪汪汪的。偶蹲下来问他怎么了？小人泣不成声，抱着我狠
: 狠的亲了几口，趴在耳朵上轻说：妈妈不要退，等我长大了我来带。咱是什么气都没有

h*n2013-09-23 07:09

38 楼

第二个看得我眼泪都要下来了，太贴心了吧~~

j*i2013-09-23 07:09

39 楼

无聊当有趣