m*******1
发帖数: 77 | 1 这个题看了不少的讲解，大概就是维护一个栈，每当找到一个右边界时，弹出所有的左
边界进行计算，但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
，leetcode上的一个测试例子是：
3,6,5,7,4,8,1,0
最大面积是4*5 = 20，但是当8作为右边界开始弹出时，6已经弹出，这样的话如何得到
左边界呢？ |
s*********s
发帖数: 140 | |
s*********s
发帖数: 140 | 3 我觉得就像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*******b
发帖数: 2586 | 4 终于会做了。。。
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*****2
发帖数: 21240 | 5
这个不错，过了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*******b
发帖数: 2586 | 6 过了，哈哈
【在 p*****2 的大作中提到】
:
: 这个不错，过了OJ了？一会儿学习一下。
|
p*****2
发帖数: 21240 | 7
上来加个0有点tricky呀。如果给定是int[]就不能那么做了。
【在 l*******b 的大作中提到】
: 过了，哈哈
|
c*****a
发帖数: 808 | 8
不用0和int[]的话，最后加上这些就可以啦
while(!stack.empty):
m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))
【在 p*****2 的大作中提到】
:
: 上来加个0有点tricky呀。如果给定是int[]就不能那么做了。
|
l*******b
发帖数: 2586 | 9 嗯，对的，本来想着还得给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*****2
发帖数: 21240 | 10
我的意思是这个trick挺好，但是面试的时候很可能用不上。
【在 c*****a 的大作中提到】
:
: 不用0和int[]的话，最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))
|
|
|
p*****2
发帖数: 21240 | 11 不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。 |
d*****9
发帖数: 90 | |
k****r
发帖数: 807 | 13 lz，测8的时候，4就已经是他的左边界了。
【在 m*******1 的大作中提到】
: 这个题看了不少的讲解，大概就是维护一个栈，每当找到一个右边界时，弹出所有的左
: 边界进行计算，但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
: ，leetcode上的一个测试例子是：
: 3,6,5,7,4,8,1,0
: 最大面积是4*5 = 20，但是当8作为右边界开始弹出时，6已经弹出，这样的话如何得到
: 左边界呢？
|
k****r
发帖数: 807 | 14 那个能装多少水的那个，我脚的比这个还难呢
【在 p*****2 的大作中提到】
: 不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。
|
b*****n
发帖数: 482 | 15 这个真是太简洁了。
今天晚上从有思路到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*****2
发帖数: 21240 | 16
装水那个我挺快想出来了。这个没想出来当时。
【在 k****r 的大作中提到】
: 那个能装多少水的那个，我脚的比这个还难呢
|
b*****n
发帖数: 482 | 17 装水那个我差了一口气，我左右两个index同时移动了。
【在 p*****2 的大作中提到】
:
: 装水那个我挺快想出来了。这个没想出来当时。
|
w****x
发帖数: 2483 | 18
//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*****2
发帖数: 21240 | 19
这个我当时想到了。不过复杂度高了些。
【在 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****x
发帖数: 2483 | 20
我觉得这题真要问的话给个二分就差不多了，又好写。
基本上写堆栈的感觉肯定是见过了
【在 p*****2 的大作中提到】
:
: 这个我当时想到了。不过复杂度高了些。
|
|
|
p*****2
发帖数: 21240 | 21 我也这么认为
【在 w****x 的大作中提到】
:
: 我觉得这题真要问的话给个二分就差不多了，又好写。
: 基本上写堆栈的感觉肯定是见过了
|
c********t
发帖数: 5706 | 22 这道题我想到的是二分法
存水题也很难想，我试图用两边夹，还是没想出，最后想了一个先找出最大数，然后左
右算分别存水量。
【在 b*****n 的大作中提到】
: 装水那个我差了一口气，我左右两个index同时移动了。
|
w****x
发帖数: 2483 | 23
其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似，都是保证一个递增或递
减序列然后通过index判断距离。
【在 c********t 的大作中提到】
: 这道题我想到的是二分法
: 存水题也很难想，我试图用两边夹，还是没想出，最后想了一个先找出最大数，然后左
: 右算分别存水量。
|
c********t
发帖数: 5706 | 24 嗯，我再复习一下体会体会
【在 w****x 的大作中提到】
:
: 其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似，都是保证一个递增或递
: 减序列然后通过index判断距离。
|
m*******1
发帖数: 77 | 25 这个题看了不少的讲解，大概就是维护一个栈，每当找到一个右边界时，弹出所有的左
边界进行计算，但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
，leetcode上的一个测试例子是：
3,6,5,7,4,8,1,0
最大面积是4*5 = 20，但是当8作为右边界开始弹出时，6已经弹出，这样的话如何得到
左边界呢？ |
s*********s
发帖数: 140 | 26 我觉得就像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*******b
发帖数: 2586 | 27 终于会做了。。。
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*****2
发帖数: 21240 | 28
这个不错，过了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*******b
发帖数: 2586 | 29 过了，哈哈
【在 p*****2 的大作中提到】
:
: 这个不错，过了OJ了？一会儿学习一下。
|
p*****2
发帖数: 21240 | 30
上来加个0有点tricky呀。如果给定是int[]就不能那么做了。
【在 l*******b 的大作中提到】
: 过了，哈哈
|
|
|
c*****a
发帖数: 808 | 31
不用0和int[]的话，最后加上这些就可以啦
while(!stack.empty):
m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))
【在 p*****2 的大作中提到】
:
: 上来加个0有点tricky呀。如果给定是int[]就不能那么做了。
|
l*******b
发帖数: 2586 | 32 嗯，对的，本来想着还得给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*****2
发帖数: 21240 | 33
我的意思是这个trick挺好，但是面试的时候很可能用不上。
【在 c*****a 的大作中提到】
:
: 不用0和int[]的话，最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))
|
p*****2
发帖数: 21240 | 34 不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。 |
d*****9
发帖数: 90 | |
k****r
发帖数: 807 | 36 lz，测8的时候，4就已经是他的左边界了。
【在 m*******1 的大作中提到】
: 这个题看了不少的讲解，大概就是维护一个栈，每当找到一个右边界时，弹出所有的左
: 边界进行计算，但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
: ，leetcode上的一个测试例子是：
: 3,6,5,7,4,8,1,0
: 最大面积是4*5 = 20，但是当8作为右边界开始弹出时，6已经弹出，这样的话如何得到
: 左边界呢？
|
k****r
发帖数: 807 | 37 那个能装多少水的那个，我脚的比这个还难呢
【在 p*****2 的大作中提到】
: 不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。
|
b*****n
发帖数: 482 | 38 这个真是太简洁了。
今天晚上从有思路到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*****2
发帖数: 21240 | 39
装水那个我挺快想出来了。这个没想出来当时。
【在 k****r 的大作中提到】
: 那个能装多少水的那个，我脚的比这个还难呢
|
b*****n
发帖数: 482 | 40 装水那个我差了一口气，我左右两个index同时移动了。
【在 p*****2 的大作中提到】
:
: 装水那个我挺快想出来了。这个没想出来当时。
|
|
|
w****x
发帖数: 2483 | 41
//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*****2
发帖数: 21240 | 42
这个我当时想到了。不过复杂度高了些。
【在 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****x
发帖数: 2483 | 43
我觉得这题真要问的话给个二分就差不多了，又好写。
基本上写堆栈的感觉肯定是见过了
【在 p*****2 的大作中提到】
:
: 这个我当时想到了。不过复杂度高了些。
|
p*****2
发帖数: 21240 | 44 我也这么认为
【在 w****x 的大作中提到】
:
: 我觉得这题真要问的话给个二分就差不多了，又好写。
: 基本上写堆栈的感觉肯定是见过了
|
c********t
发帖数: 5706 | 45 这道题我想到的是二分法
存水题也很难想，我试图用两边夹，还是没想出，最后想了一个先找出最大数，然后左
右算分别存水量。
【在 b*****n 的大作中提到】
: 装水那个我差了一口气，我左右两个index同时移动了。
|
w****x
发帖数: 2483 | 46
其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似，都是保证一个递增或递
减序列然后通过index判断距离。
【在 c********t 的大作中提到】
: 这道题我想到的是二分法
: 存水题也很难想，我试图用两边夹，还是没想出，最后想了一个先找出最大数，然后左
: 右算分别存水量。
|
c********t
发帖数: 5706 | 47 嗯，我再复习一下体会体会
【在 w****x 的大作中提到】
:
: 其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似，都是保证一个递增或递
: 减序列然后通过index判断距离。
|
s*****n
发帖数: 994 | 48 挖个旧坑再问这道题
对于每个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();
|
