议员没回复怎么办？ - 未名空间MITBBS历史存档

议员没回复怎么办？# EB23 - 劳工卡

m*12015-03-19 07:03

1 楼

这个题看了不少的讲解，大概就是维护一个栈，每当找到一个右边界时，弹出所有的左
边界进行计算，但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
，leetcode上的一个测试例子是：
3,6,5,7,4,8,1,0
最大面积是4*5 = 20，但是当8作为右边界开始弹出时，6已经弹出，这样的话如何得到
左边界呢？

b*12015-03-19 07:03

2 楼

3/9 联系议员，到今天也没回复。打到office问过，确实收到我的fax。
要再打电话问吗？眼看就倒退了！悲催啊！

s*s2015-03-19 07:03

3 楼

我看到的一种解法是用stack存短的bar，而不是存边界。http://tech-queries.blogspot.com/2011/03/maximum-area-rectangle-in-histogram.html

B*y2015-03-19 07:03

4 楼

you got 2 senators and 1 congressman in your district, right?

s*s2015-03-19 07:03

5 楼

我觉得就像http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html 里面说的，stack存的是started but yet unfinished subhistograms. 而且stack存的是高度的index，不是高度本身。你要是只存高度，那宽度的信息就丢失了。比如在你要得到4*5=20这个结果的时候，应该是iterate到了1，在将要弹出4的高度的时候，此时的stack应该是[3的index:0] -> [4的index:4]. 那rectangle的宽度是根据3的index0和1的index6来算的，就是6-0 - 1 = 5.

b*12015-03-19 07:03

6 楼

I contacted all of them and none responded so far.
Anything could I do?

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

: you got 2 senators and 1 congressman in your district, right?

l*b2015-03-19 07:03

7 楼

终于会做了。。。
int largestRectArea(vector &h) {
stack p;
int i = 0, m = 0;
h.push_back(0);
while(i < h.size()) {
if(p.empty() || h[p.top()] <= h[i])
p.push(i++);
else {
int t = p.top();
p.pop();
m = max(m, h[t] * (p.empty() ? i : i - p.top() - 1 ));
}
}
return m;
}

B*y2015-03-19 07:03

8 楼

call their offices

p*22015-03-19 07:03

9 楼

这个不错，过了OJ了？一会儿学习一下。

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

: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

l*b2015-03-19 07:03

10 楼

过了，哈哈

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

:
: 这个不错，过了OJ了？一会儿学习一下。

p*22015-03-19 07:03

11 楼

上来加个0有点tricky呀。如果给定是int[]就不能那么做了。

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

: 过了，哈哈

c*a2015-03-19 07:03

12 楼

不用0和int[]的话，最后加上这些就可以啦
while(!stack.empty):
m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

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

:
: 上来加个0有点tricky呀。如果给定是int[]就不能那么做了。

l*b2015-03-19 07:03

13 楼

嗯，对的，本来想着还得给while里加好几句，所以才给h里push了个0，强制把stack都
弹出来

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

:
: 不用0和int[]的话，最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

p*22015-03-19 07:03

14 楼

我的意思是这个trick挺好，但是面试的时候很可能用不上。

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

:
: 不用0和int[]的话，最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

p*22015-03-19 07:03

15 楼

不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。

d*92015-03-19 07:03

16 楼

这个和那个山上存雨水的问题有共通之处吧？

k*r2015-03-19 07:03

17 楼

lz，测8的时候，4就已经是他的左边界了。

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

: 这个题看了不少的讲解，大概就是维护一个栈，每当找到一个右边界时，弹出所有的左
: 边界进行计算，但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
: ，leetcode上的一个测试例子是：
: 3,6,5,7,4,8,1,0
: 最大面积是4*5 = 20，但是当8作为右边界开始弹出时，6已经弹出，这样的话如何得到
: 左边界呢？

k*r2015-03-19 07:03

18 楼

那个能装多少水的那个，我脚的比这个还难呢

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

: 不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。

b*n2015-03-19 07:03

19 楼

这个真是太简洁了。
今天晚上从有思路到AC，吭哧吭哧花了40分钟，一看二爷给了5分的难度，还挺高兴的
。到这儿一看“菜鸟”的code，才是我的1/3，膜拜。 orz

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

: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

p*22015-03-19 07:03

20 楼

装水那个我挺快想出来了。这个没想出来当时。

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

: 那个能装多少水的那个，我脚的比这个还难呢

b*n2015-03-19 07:03

21 楼

装水那个我差了一口气，我左右两个index同时移动了。

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

:
: 装水那个我挺快想出来了。这个没想出来当时。

w*x2015-03-19 07:03

22 楼

//a binary search solution
int GetBiggestRectBin(int a[], int n)
{
if (n <= 0) return 0;
assert(a);
int nMinIndex = 0;
for (int i = 1; i < n; i++)
if (a[nMinIndex] > a[i])
nMinIndex = i;

int nCur = a[nMinIndex] * n;
int nLft = GetBiggestRectBin(a, nMinIndex);
int nRgt = GetBiggestRectBin(a + nMinIndex + 1, n - 1 -nMinIndex);
return max(nCur, max(nLft, nRgt));
}

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

: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

p*22015-03-19 07:03

23 楼

这个我当时想到了。不过复杂度高了些。

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

:
: //a binary search solution
: int GetBiggestRectBin(int a[], int n)
: {
: if (n <= 0) return 0;
: assert(a);
: int nMinIndex = 0;
: for (int i = 1; i < n; i++)
: if (a[nMinIndex] > a[i])
: nMinIndex = i;

w*x2015-03-19 07:03

24 楼

我觉得这题真要问的话给个二分就差不多了，又好写。
基本上写堆栈的感觉肯定是见过了

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

:
: 这个我当时想到了。不过复杂度高了些。

p*22015-03-19 07:03

25 楼

我也这么认为

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

:
: 我觉得这题真要问的话给个二分就差不多了，又好写。
: 基本上写堆栈的感觉肯定是见过了

c*t2015-03-19 07:03

26 楼

这道题我想到的是二分法
存水题也很难想，我试图用两边夹，还是没想出，最后想了一个先找出最大数，然后左
右算分别存水量。

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

: 装水那个我差了一口气，我左右两个index同时移动了。

w*x2015-03-19 07:03

27 楼

其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似，都是保证一个递增或递
减序列然后通过index判断距离。

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

: 这道题我想到的是二分法
: 存水题也很难想，我试图用两边夹，还是没想出，最后想了一个先找出最大数，然后左
: 右算分别存水量。

c*t2015-03-19 07:03

28 楼

嗯，我再复习一下体会体会

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

:
: 其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似，都是保证一个递增或递
: 减序列然后通过index判断距离。

m*12015-03-19 07:03

29 楼

这个题看了不少的讲解，大概就是维护一个栈，每当找到一个右边界时，弹出所有的左
边界进行计算，但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
，leetcode上的一个测试例子是：
3,6,5,7,4,8,1,0
最大面积是4*5 = 20，但是当8作为右边界开始弹出时，6已经弹出，这样的话如何得到
左边界呢？

s*s2015-03-19 07:03

30 楼

我觉得就像http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html 里面说的，stack存的是started but yet unfinished subhistograms. 而且stack存的是高度的index，不是高度本身。你要是只存高度，那宽度的信息就丢失了。比如在你要得到4*5=20这个结果的时候，应该是iterate到了1，在将要弹出4的高度的时候，此时的stack应该是[3的index:0] -> [4的index:4]. 那rectangle的宽度是根据3的index0和1的index6来算的，就是6-0 - 1 = 5.

l*b2015-03-19 07:03

31 楼

终于会做了。。。
int largestRectArea(vector &h) {
stack p;
int i = 0, m = 0;
h.push_back(0);
while(i < h.size()) {
if(p.empty() || h[p.top()] <= h[i])
p.push(i++);
else {
int t = p.top();
p.pop();
m = max(m, h[t] * (p.empty() ? i : i - p.top() - 1 ));
}
}
return m;
}

p*22015-03-19 07:03

32 楼

这个不错，过了OJ了？一会儿学习一下。

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

: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

l*b2015-03-19 07:03

33 楼

过了，哈哈

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

:
: 这个不错，过了OJ了？一会儿学习一下。

p*22015-03-19 07:03

34 楼

上来加个0有点tricky呀。如果给定是int[]就不能那么做了。

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

: 过了，哈哈

c*a2015-03-19 07:03

35 楼

不用0和int[]的话，最后加上这些就可以啦
while(!stack.empty):
m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

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

:
: 上来加个0有点tricky呀。如果给定是int[]就不能那么做了。

l*b2015-03-19 07:03

36 楼

嗯，对的，本来想着还得给while里加好几句，所以才给h里push了个0，强制把stack都
弹出来

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

:
: 不用0和int[]的话，最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

p*22015-03-19 07:03

37 楼

我的意思是这个trick挺好，但是面试的时候很可能用不上。

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

:
: 不用0和int[]的话，最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

p*22015-03-19 07:03

38 楼

不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。

d*92015-03-19 07:03

39 楼

这个和那个山上存雨水的问题有共通之处吧？

k*r2015-03-19 07:03

40 楼

lz，测8的时候，4就已经是他的左边界了。

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

: 这个题看了不少的讲解，大概就是维护一个栈，每当找到一个右边界时，弹出所有的左
: 边界进行计算，但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
: ，leetcode上的一个测试例子是：
: 3,6,5,7,4,8,1,0
: 最大面积是4*5 = 20，但是当8作为右边界开始弹出时，6已经弹出，这样的话如何得到
: 左边界呢？

k*r2015-03-19 07:03

41 楼

那个能装多少水的那个，我脚的比这个还难呢

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

: 不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。

b*n2015-03-19 07:03

42 楼

这个真是太简洁了。
今天晚上从有思路到AC，吭哧吭哧花了40分钟，一看二爷给了5分的难度，还挺高兴的
。到这儿一看“菜鸟”的code，才是我的1/3，膜拜。 orz

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

: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

p*22015-03-19 07:03

43 楼

装水那个我挺快想出来了。这个没想出来当时。

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

: 那个能装多少水的那个，我脚的比这个还难呢

b*n2015-03-19 07:03

44 楼

装水那个我差了一口气，我左右两个index同时移动了。

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

:
: 装水那个我挺快想出来了。这个没想出来当时。

w*x2015-03-19 07:03

45 楼

//a binary search solution
int GetBiggestRectBin(int a[], int n)
{
if (n <= 0) return 0;
assert(a);
int nMinIndex = 0;
for (int i = 1; i < n; i++)
if (a[nMinIndex] > a[i])
nMinIndex = i;

int nCur = a[nMinIndex] * n;
int nLft = GetBiggestRectBin(a, nMinIndex);
int nRgt = GetBiggestRectBin(a + nMinIndex + 1, n - 1 -nMinIndex);
return max(nCur, max(nLft, nRgt));
}

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

: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

p*22015-03-19 07:03

46 楼

这个我当时想到了。不过复杂度高了些。

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

:
: //a binary search solution
: int GetBiggestRectBin(int a[], int n)
: {
: if (n <= 0) return 0;
: assert(a);
: int nMinIndex = 0;
: for (int i = 1; i < n; i++)
: if (a[nMinIndex] > a[i])
: nMinIndex = i;

w*x2015-03-19 07:03

47 楼

我觉得这题真要问的话给个二分就差不多了，又好写。
基本上写堆栈的感觉肯定是见过了

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

:
: 这个我当时想到了。不过复杂度高了些。

p*22015-03-19 07:03

48 楼

我也这么认为

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

:
: 我觉得这题真要问的话给个二分就差不多了，又好写。
: 基本上写堆栈的感觉肯定是见过了

c*t2015-03-19 07:03

49 楼

这道题我想到的是二分法
存水题也很难想，我试图用两边夹，还是没想出，最后想了一个先找出最大数，然后左
右算分别存水量。

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

: 装水那个我差了一口气，我左右两个index同时移动了。

w*x2015-03-19 07:03

50 楼

其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似，都是保证一个递增或递
减序列然后通过index判断距离。

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

: 这道题我想到的是二分法
: 存水题也很难想，我试图用两边夹，还是没想出，最后想了一个先找出最大数，然后左
: 右算分别存水量。

c*t2015-03-19 07:03

51 楼

嗯，我再复习一下体会体会

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

:
: 其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似，都是保证一个递增或递
: 减序列然后通过index判断距离。

s*n2015-03-19 07:03

52 楼

挖个旧坑再问这道题
对于每个i，如果进到else｛｝中，为什么只要求和上一个top之间的面积？为什么不能
是和top下面的height形成的矩形面积更大？

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

: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();