x***i
发帖数: 64 | 1 原来在版里看到过code,现在找不到了。哪位好心可以再贴一下吗？ |
f*******t
发帖数: 7549 | 2 int water(int * a, int n) {
stack > mystack;
int water = 0;
for(int i = 0; i
while(!mystack.empty() && mystack.top().second <= a[i]) {
int bottom = mystack.top().second;
mystack.pop();
if( mystack.empty())
break;
int top = mystack.top().second < a[i]? mystack.top().second: a[i];
int length = i - mystack.top().first - 1;
water = water + (top-bottom)* length;
}
mystack.push(make_pair(i, a[i]));
}
return water;
} |
x***i
发帖数: 64 | 3 多谢多谢。。。
除了大小比较和边界处理不一样，算法和最大rectangle一致。
http://wansishuang.appspot.com/?p=3002
【在 f*******t 的大作中提到】
: int water(int * a, int n) {
: stack > mystack;
: int water = 0;
:
: for(int i = 0; i: while(!mystack.empty() && mystack.top().second <= a[i]) {
: int bottom = mystack.top().second;
: mystack.pop();
: if( mystack.empty())
: break;
|
g**********y
发帖数: 14569 | 4 G的标准解法是：找到最高的bar, 分别算左边和右边，那个解写起来长一点，但是解释
简单，不容易错。
public int hold2(int[] a) {
int h = 0;
int N = a.length;
for (int i=1; i a[h]) h = i;
int total = 0;
int left = a[0];
for (int i=1; i
if (a[i] > left) {
left = a[i];
}
else {
total += left - a[i];
}
}
int right = a[N-1];
for (int i=N-2; i>h; i--) {
if (a[i] > right) {
right = a[i];
}
else {
total += right - a[i];
}
}
return total;
}
【在 f*******t 的大作中提到】
: int water(int * a, int n) {
: stack > mystack;
: int water = 0;
:
: for(int i = 0; i: while(!mystack.empty() && mystack.top().second <= a[i]) {
: int bottom = mystack.top().second;
: mystack.pop();
: if( mystack.empty())
: break;
|
I***A
发帖数: 6 | 5 能不能讲讲具体的题目啊？ 考古了一下，但没有找到具体的描述； 那位大虾给
讲讲，谢谢！ |
f*******t
发帖数: 7549 | 6 这个好
【在 g**********y 的大作中提到】
: G的标准解法是：找到最高的bar, 分别算左边和右边，那个解写起来长一点，但是解释
: 简单，不容易错。
: public int hold2(int[] a) {
: int h = 0;
: int N = a.length;
: for (int i=1; i a[h]) h = i;
:
: int total = 0;
: int left = a[0];
: for (int i=1; i
|
f*******t
发帖数: 7549 | 7 一个表示直方图高度的数组，每格宽度为1，求能蓄多少水。
比如数组[1, 0, 1]能蓄1单位水，[2, 1, 0, 2]能蓄3单位。
【在 I***A 的大作中提到】
: 能不能讲讲具体的题目啊？ 考古了一下，但没有找到具体的描述； 那位大虾给
: 讲讲，谢谢！
|
Y**B
发帖数: 144 | 8 直方图最大矩形和最大蓄水什么关系？ 怎么个蓄水法？ |
A**u
发帖数: 2458 | 9 有没有分治解法
【在 x***i 的大作中提到】
: 多谢多谢。。。
: 除了大小比较和边界处理不一样，算法和最大rectangle一致。
: http://wansishuang.appspot.com/?p=3002
|
k****n
发帖数: 369 | 10 这题最快就是O(n)，分治也不可能比这个快了
【在 A**u 的大作中提到】
: 有没有分治解法
|
|
|
m*****k
发帖数: 731 | |
A**u
发帖数: 2458 | 12 大牛 能不能讲解一下
这个算法为啥是对的？ 我看不懂.
假设栈里元素为 AB. (B>A)。
读入C, C < A
那么 AB 都pop出.
难道不存在这样的可能性吗: 将来某个时候，可以以A开头，形式最大的面积?
【在 k****n 的大作中提到】
: 这题最快就是O(n)，分治也不可能比这个快了
|
k*n
发帖数: 150 | 13 我的解法跟堆栈没关系
就是从左边和右边分别扫描一遍
记录迄今为止的最大值就可以了
【在 A**u 的大作中提到】
: 大牛 能不能讲解一下
: 这个算法为啥是对的？ 我看不懂.
: 假设栈里元素为 AB. (B>A)。
: 读入C, C < A
: 那么 AB 都pop出.
: 难道不存在这样的可能性吗: 将来某个时候，可以以A开头，形式最大的面积?
|
A**u
发帖数: 2458 | 14 你的解法在哪呢
贴出来，学习学习
【在 k*n 的大作中提到】
: 我的解法跟堆栈没关系
: 就是从左边和右边分别扫描一遍
: 记录迄今为止的最大值就可以了
|
Y**B
发帖数: 144 | 15 2,1,0,2 为啥是3????
【在 f*******t 的大作中提到】
: 一个表示直方图高度的数组，每格宽度为1，求能蓄多少水。
: 比如数组[1, 0, 1]能蓄1单位水，[2, 1, 0, 2]能蓄3单位。
|
H***e
发帖数: 476 | 16 喔。名白了。
是用每个 小矩阵得夹缝盛水
【在 Y**B 的大作中提到】
: 2,1,0,2 为啥是3????
|
s******n
发帖数: 3946 | 17 显然不对啊，假设a[0]=a[1]=...=a[N]=10，你程序出来结果是0
【在 g**********y 的大作中提到】
: G的标准解法是：找到最高的bar, 分别算左边和右边，那个解写起来长一点，但是解释
: 简单，不容易错。
: public int hold2(int[] a) {
: int h = 0;
: int N = a.length;
: for (int i=1; i a[h]) h = i;
:
: int total = 0;
: int left = a[0];
: for (int i=1; i
|
H***e
发帖数: 476 | 18 晕
本来就是0
【在 s******n 的大作中提到】
: 显然不对啊，假设a[0]=a[1]=...=a[N]=10，你程序出来结果是0
|
s******n
发帖数: 3946 | 19 能盛容量为0的水？
【在 H***e 的大作中提到】
: 晕
: 本来就是0
|
Y**B
发帖数: 144 | |
|
|
C***y
发帖数: 2546 | 21 谁能稍微解释一下题目？
没看明白要求
【在 x***i 的大作中提到】
: 原来在版里看到过code,现在找不到了。哪位好心可以再贴一下吗？
|
H***e
发帖数: 476 | 22 就是凹下去的才能盛水
【在 C***y 的大作中提到】
: 谁能稍微解释一下题目？
: 没看明白要求
|
C***y
发帖数: 2546 | 23 每个bar是连通的吗？
【在 H***e 的大作中提到】
: 就是凹下去的才能盛水
|
H***e
发帖数: 476 | 24 每个bar是不联通的，你把bar想象成实心的，上面盛水
【在 C***y 的大作中提到】
: 每个bar是连通的吗？
|
s******n
发帖数: 3946 | 25 ic
【在 H***e 的大作中提到】
: 每个bar是不联通的，你把bar想象成实心的，上面盛水
|
C***y
发帖数: 2546 | 26 明白了！
谢谢！
【在 H***e 的大作中提到】
: 每个bar是不联通的，你把bar想象成实心的，上面盛水
|
