g***s 发帖数: 3811 | 1 当年同事去google面试的题目。
给你n个数字a1,a2...an,表示坐标上面(i,ai)个点,i=1.. n
(i,ai)到(i,0)共n个线段,从中挑两条,和x轴一起构成一个容器,让容器能装
的液体容量最大
(容器不能倾斜)。
大家先做做 | g*********s 发帖数: 1782 | 2 这不就是maximum rectangle in histogram吗。
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 当年同事去google面试的题目。 : 给你n个数字a1,a2...an,表示坐标上面(i,ai)个点,i=1.. n : (i,ai)到(i,0)共n个线段,从中挑两条,和x轴一起构成一个容器,让容器能装 : 的液体容量最大 : (容器不能倾斜)。 : 大家先做做
| g***s 发帖数: 3811 | 3 haha. 原来是老题。
这题作为acm试题基本就是送分啊
【在 g*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这不就是maximum rectangle in histogram吗。
| g*********s 发帖数: 1782 | 4 对没受过训练的人来说还是有难度。
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : haha. 原来是老题。 : 这题作为acm试题基本就是送分啊
| H*M 发帖数: 1268 | 5 it is different
【在 g*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这不就是maximum rectangle in histogram吗。
| g***s 发帖数: 3811 | 6 you are right. i didnt read the "maximum rectangle in histogram"
carefully.
but we can also find a O(n) for this question.
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : it is different
| f*********i 发帖数: 197 | 7 DP?
假设input是一个数组,从0到n,那么我们要的是以下三种情况中最大的那个
for the ith and jth position
1) min(a[i],a[j])*(j-i)
2) min(a[i+1],a[j])*(j-i-1)
3) min(a[i],a[j-1])*(j-i-1)
i一开始从0, j一开始从n
按照这样不断DP 递归去找最大的,时间复杂度应该还是O(n) | f*********i 发帖数: 197 | 8 JAVA代码如下:
另外,如果ai可以是负数,那么一开始就要分割为正数和负数两个不同的数列,同时用0代
替异常的数,比如:{1,-4,5,-3,-6,6,7}
=> {1,0,5,0,0,6,7} and {0,-4,0,-3,-6,0,0},然后对负数列取绝对值.
public static int array_maximum_bucket(int [] arr, int start, int end){
if(start>=end)
return 0;
int height = arr[start]>=arr[end]?arr[end]:arr[start];
return find_max(height*(end-start),array_maximum_bucket(arr, start+1,
end),array_maximum_bucket(arr,start,end-1));
}
public static int find_max(int i, int j, int k){
int max = i;
if(j>max)
max = j;
if(k>max)
max = k;
return max;
} | b********h 发帖数: 119 | 9 你这个是O(n^2)的吧
【在 f*********i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : DP? : 假设input是一个数组,从0到n,那么我们要的是以下三种情况中最大的那个 : for the ith and jth position : 1) min(a[i],a[j])*(j-i) : 2) min(a[i+1],a[j])*(j-i-1) : 3) min(a[i],a[j-1])*(j-i-1) : i一开始从0, j一开始从n : 按照这样不断DP 递归去找最大的,时间复杂度应该还是O(n)
| b*k 发帖数: 27 | 10 O(nlog(n)) solution:
Using DP in general:
sort (i, ai) by ai take O(nlog(n))
got (i_1, ai_1), (i_2, ai_2), .... (i_n, ai_n)
where ai_1 >= ai_2 >= ... ai_n
then keep a minHeap and maxHeap for i_k
maxInfo.cap = -INF;
for (each i_k from (i_1 to i_n))
i_min = minHeap.getMin();
i_max = maxHeap.getMax();
tmpCap = ai_k*(max(abs(i_k - i_min), abs(i_k - i_max)))
if (tmpCap > maxInfo.cap)
maxInfo.cap = tmpCap
//book keeping the i_k, and i_min or i_max
minHeap.insert(i_k) //log(n)
maxHeap.insert(i_k) //log(n)
end
Thinking hard for an O(n) solution, anyone knows?
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 当年同事去google面试的题目。 : 给你n个数字a1,a2...an,表示坐标上面(i,ai)个点,i=1.. n : (i,ai)到(i,0)共n个线段,从中挑两条,和x轴一起构成一个容器,让容器能装 : 的液体容量最大 : (容器不能倾斜)。 : 大家先做做
| | | b*k 发帖数: 27 | 11 don't need to maintain heaps, just maintain the value of max and min of
i_k has been scanned so for.
Anyway, the sort part takes O(nlog(n))
【在 b*k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(nlog(n)) solution: : Using DP in general: : sort (i, ai) by ai take O(nlog(n)) : got (i_1, ai_1), (i_2, ai_2), .... (i_n, ai_n) : where ai_1 >= ai_2 >= ... ai_n : then keep a minHeap and maxHeap for i_k : maxInfo.cap = -INF; : for (each i_k from (i_1 to i_n)) : i_min = minHeap.getMin(); : i_max = maxHeap.getMax();
| y******5 发帖数: 43 | 12 Brute Force: O(n^2)
D & C: O(nlgn)
Stack linear search: O(n)
It is an ACM question.
You can get the explanation here: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
【在 b*k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(nlog(n)) solution: : Using DP in general: : sort (i, ai) by ai take O(nlog(n)) : got (i_1, ai_1), (i_2, ai_2), .... (i_n, ai_n) : where ai_1 >= ai_2 >= ... ai_n : then keep a minHeap and maxHeap for i_k : maxInfo.cap = -INF; : for (each i_k from (i_1 to i_n)) : i_min = minHeap.getMin(); : i_max = maxHeap.getMax();
| u******e 发帖数: 758 | 13 都说不是直方柱内接矩形问题了
【在 y******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Brute Force: O(n^2) : D & C: O(nlgn) : Stack linear search: O(n) : It is an ACM question. : You can get the explanation here: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
| y******5 发帖数: 43 | 14 You should not expect the interviewer asks the question without changing a
word.
【在 u******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 都说不是直方柱内接矩形问题了
| g*******y 发帖数: 1930 | 15
有非stack的o(n)方法,我以前没看stack的solution时候想到的,不过现在没太多时间
码字。
大概的基本思路就是,考虑这个问题:现在你要做的是,寻找并记录下:对于直方图的
每一个bar,左边第一个比它更高的
bar的位置 + 右边第一个比它更高的bar的位置。
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 当年同事去google面试的题目。 : 给你n个数字a1,a2...an,表示坐标上面(i,ai)个点,i=1.. n : (i,ai)到(i,0)共n个线段,从中挑两条,和x轴一起构成一个容器,让容器能装 : 的液体容量最大 : (容器不能倾斜)。 : 大家先做做
| u******e 发帖数: 758 | 16 input
2 1 2
in histogram result is 3 (width=3 * height*1)
in this question result is 4 (width=2 * height*2)
how do you use stack?
【在 y******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : You should not expect the interviewer asks the question without changing a : word.
| y******5 发帖数: 43 | 17 Hint:
If input 2, 1, 2
there is only 1 bar
if input 1, 2, 3 or 3, 2, 1
there are 2 bars
【在 u******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : input : 2 1 2 : in histogram result is 3 (width=3 * height*1) : in this question result is 4 (width=2 * height*2) : how do you use stack?
| b*******y 发帖数: 1240 | 18 什么是bar
【在 y******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Hint: : If input 2, 1, 2 : there is only 1 bar : if input 1, 2, 3 or 3, 2, 1 : there are 2 bars
| u******e 发帖数: 758 | 19 还是不太明白
【在 y******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Hint: : If input 2, 1, 2 : there is only 1 bar : if input 1, 2, 3 or 3, 2, 1 : there are 2 bars
| y******5 发帖数: 43 | 20 Sorry for confusing. I mean histogram. "bar" is from bar chart.
【在 b*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 什么是bar
| | | u******e 发帖数: 758 | 21 could you explan more detail how to solve case
2 1 2
in this problem with stack?
【在 y******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Sorry for confusing. I mean histogram. "bar" is from bar chart.
| y******5 发帖数: 43 | 22 I mean, we need to find a way to construct histogram, and we can start from
min of leftmost and rightmost. Suppose current value a[i] is no less than
next value (a[i-1] or a[i+1]), then overwrite the next value with a[i]. At
the end, you will have n-1 histograms.
【在 u******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还是不太明白
| y******5 发帖数: 43 | 23 Sorry guys, my previous construction method is not correct. New method to
construct histogram is:
Step:
1. maintain 3 variables: left, right, min. left =1, right=n, min_height=0
2. min_height = min(a[left], a[right])
3. if min_height == a[left], left++ until a[left] > min_height, and all
elements just scaned are assigned to min_height;
else if min_height == a[right], right-- until a[right] > min_height, and
all elements just scaned are assigned to min_height;
4. goto step 2 until left + 1 = right. Suppose a[left] > a[right], then a[
left] = a[right]
Now we have n-1 histograms. Please correct me if I am wrong.
from
【在 y******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I mean, we need to find a way to construct histogram, and we can start from : min of leftmost and rightmost. Suppose current value a[i] is no less than : next value (a[i-1] or a[i+1]), then overwrite the next value with a[i]. At : the end, you will have n-1 histograms.
| u******e 发帖数: 758 | 24 明白了
from
【在 y******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I mean, we need to find a way to construct histogram, and we can start from : min of leftmost and rightmost. Suppose current value a[i] is no less than : next value (a[i-1] or a[i+1]), then overwrite the next value with a[i]. At : the end, you will have n-1 histograms.
| y******5 发帖数: 43 | 25 In your case, a[1] == a[3] == 2, so we just start from a[1] and move
rightward. a[2] is less than 2, so assign 2 to a[2]. Because a[2] and a[3]
are adjacent, we stop here and will have {2,2,2}, which can be seen as two
histograms.
【在 u******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : could you explan more detail how to solve case : 2 1 2 : in this problem with stack?
| m***g 发帖数: 90 | 26 弱问,这是立体坐标么? 没看懂怎么跟x轴形成立体矩形..
a1
0 .......i........
a2
..an
thanks
这不就是maximum rectangle in histogram吗。
【在 g*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这不就是maximum rectangle in histogram吗。
| h*********3 发帖数: 111 | 27
我想的一个方法,大家看看。
先拿 (1,a1) 和 (n,an) 这2个点,计算容量,(假设a1<=an), 那就是
a1 * (n-1), 存为当前最大 CurMax, i.e. CurMax = a1 * (n-1)
然后我们从小的那个边开始扫,a1
小,就看a3,一直到某个ai, ai>a1, 这时计算容量, temp = min(ai,an)*(n-i),
CurMax = max(CurMax,temp); 再看ai 和an 哪个小,如果ai小,接着往下扫 a(i+1).
.. 只知道某个数aj , aj> ai; 如果an小,就看 a(n-1)...知道某个数 ak, ak>an.
然后再计算容量,更新CurMax。 重复做这些,直到两条边重合。CurMax里存的就是最
大的容量。
复杂度 O(n).
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 当年同事去google面试的题目。 : 给你n个数字a1,a2...an,表示坐标上面(i,ai)个点,i=1.. n : (i,ai)到(i,0)共n个线段,从中挑两条,和x轴一起构成一个容器,让容器能装 : 的液体容量最大 : (容器不能倾斜)。 : 大家先做做
| s*****y 发帖数: 897 | 28 Seems not right
given the following input
4, 3, 1, 2, 5
Your first CurMax is already wrong value le.
Look at this:
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram
a1
).
【在 h*********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我想的一个方法,大家看看。 : 先拿 (1,a1) 和 (n,an) 这2个点,计算容量,(假设a1<=an), 那就是 : a1 * (n-1), 存为当前最大 CurMax, i.e. CurMax = a1 * (n-1) : 然后我们从小的那个边开始扫,a1: 小,就看a3,一直到某个ai, ai>a1, 这时计算容量, temp = min(ai,an)*(n-i), : CurMax = max(CurMax,temp); 再看ai 和an 哪个小,如果ai小,接着往下扫 a(i+1). : .. 只知道某个数aj , aj> ai; 如果an小,就看 a(n-1)...知道某个数 ak, ak>an. : 然后再计算容量,更新CurMax。 重复做这些,直到两条边重合。CurMax里存的就是最 : 大的容量。
| h*********3 发帖数: 111 | 29 前面有人已经提过了,这提不是那个经典的 histogram题目。
你的例子,最大值是16. 就是4和5和x轴形成的容器。
【在 s*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Seems not right : given the following input : 4, 3, 1, 2, 5 : Your first CurMax is already wrong value le. : Look at this: : http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram : : a1 : ).
| s*****y 发帖数: 897 | 30 o, you are right.
Then it is actually easier than the ACM question.
【在 h*********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 前面有人已经提过了,这提不是那个经典的 histogram题目。 : 你的例子,最大值是16. 就是4和5和x轴形成的容器。
| | | j*j 发帖数: 5564 | 31 恩,这个跟直方图问题不一样
如果ai是负数,那么它参与构成的容器盛不住液体,这些数一定得过滤掉;所以我们不
妨简单化一下,假定ai都是positive的
可以用两个queue来做,q1, q2
先做1->n的loop, 根据逐次增大的ai 把(i, ai) push 到 q1
再做n->1的loop, 也根据逐次增大的ai 把 (i, ai) push 到 q2
同时从q1和q2 pop Aq11, Aq21,计算构成的rectangle面积,作为初始的最大容积max;
比较Aq11和Aq21的大小,pop小的所对应的queue, 假定pop出Aq12, 计算出Aq12和Aq21
的rectangle面积,跟max比较,大的话就替代max;
这样一直做下去,直到最后q1,q2为空
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 当年同事去google面试的题目。 : 给你n个数字a1,a2...an,表示坐标上面(i,ai)个点,i=1.. n : (i,ai)到(i,0)共n个线段,从中挑两条,和x轴一起构成一个容器,让容器能装 : 的液体容量最大 : (容器不能倾斜)。 : 大家先做做
| g***s 发帖数: 3811 | 32 31楼和27楼其实是一个意思。
ACM那题是不同的一题,其实可以用我们熟悉大DP来解
1 求all b(x), b(x)=在x右边第一比ax小的位置 [b(x)=n+1 if all are larger than
ax] O(n) using DP
2 求all c(x), c(x)=在x左边最后一个比ax小的位置[c(x)=0 if all are larger than
ax] O(n) using DP
3 d(x) = (b(x) - c(x) -1) * ax O(n)
4 return max(d(x)) | g*****i 发帖数: 19 | 33 这题和largest rectangle of histogram 不是一回事,但很简单,有 O(n)算法。
The principle of optimization is: any A[k]>= min(A[optimal_left], A[optima_
right]) must satisfy optimal_left<=k<=optimal_right
(1)scan the array A[], find two elements (A[current_left], A[current_right
]) with largest and second largest value respectively, set the current
optimal area as min(A[current_left], A[current_right])*(current_right-
current_left)
(2) scan the array A[] again, test if the select element can replace the A[
current_left] when its index is smaller than current_left, otherwise, if can
replace the A[current_right], by comparing the area with the current
optimal area
(3) finally the current_left and current_right is the optimal.
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 当年同事去google面试的题目。 : 给你n个数字a1,a2...an,表示坐标上面(i,ai)个点,i=1.. n : (i,ai)到(i,0)共n个线段,从中挑两条,和x轴一起构成一个容器,让容器能装 : 的液体容量最大 : (容器不能倾斜)。 : 大家先做做
| g***s 发帖数: 3811 | 34 这个不对。
A[optima_
A[current_right
the A[
can
【在 g*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题和largest rectangle of histogram 不是一回事,但很简单,有 O(n)算法。 : The principle of optimization is: any A[k]>= min(A[optimal_left], A[optima_ : right]) must satisfy optimal_left<=k<=optimal_right : (1)scan the array A[], find two elements (A[current_left], A[current_right : ]) with largest and second largest value respectively, set the current : optimal area as min(A[current_left], A[current_right])*(current_right- : current_left) : (2) scan the array A[] again, test if the select element can replace the A[ : current_left] when its index is smaller than current_left, otherwise, if can : replace the A[current_right], by comparing the area with the current
| n*******t 发帖数: 77 | 35
than
than
b(x)怎样DP能O(n)?
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 31楼和27楼其实是一个意思。 : ACM那题是不同的一题,其实可以用我们熟悉大DP来解 : 1 求all b(x), b(x)=在x右边第一比ax小的位置 [b(x)=n+1 if all are larger than : ax] O(n) using DP : 2 求all c(x), c(x)=在x左边最后一个比ax小的位置[c(x)=0 if all are larger than : ax] O(n) using DP : 3 d(x) = (b(x) - c(x) -1) * ax O(n) : 4 return max(d(x))
| g***s 发帖数: 3811 | | d*******l 发帖数: 338 | 37 我得想法和27楼差不多。
我觉得两边可以维护一个起始和结束的指针l和r.这个问题的一个性质是,如果某个bar
的左边有比它高的bar,那最优解必然不可能以它为起始,因为我们总能把边界再往左
扩,所以l递增的时候可以直接略过比当前最大值小的那些ai,相当于只检查一个递增
的序列。对于每个要检查的元素,结束指针r要往回退到第一个大于等于al的元素,对
经过的所有元素都尝试更新最大值。这样两边的指针相遇就停止,复杂度是O(n). | g**e 发帖数: 6127 | 38 /**
Maintain two pointers, head and tail,
1. start sweeping the array from head if a[head]
otherwise
2. for each a[i], if current value is less or equal to a[head] (or a[tail]),
skip
3. else compute area with a[i] & a[tail] (or a[head]), set start=i (or stop=
i), update max volume if necessary
4. until head meets tail, return max volume
All items are scanned at most once, total time O(n).
*/
public static int maxVolume(int[] a) {
if (a.length<=1)
return 0;
int maxVolume = 0;
int start = 0, end = a.length-1;
int maxStart = 0, maxStop = a.length-1;
maxVolume = Math.min(a[start], a[end]) * (end - start);
while (start
//move start pointer
if (a[start]
int i = start;
//move forward for all a[i]<=a[start]
while (i
i++;
if (i==end)
break;
else {
//a[i]>a[start], compare volumn
int tmp = Math.min(a[i], a[end]) * (end-i);
if ( tmp>maxVolume ) {
maxVolume = tmp;
maxStart = i;
}
start = i; //update start pointer to i
}
} else { //move end pointer
int i = end;
//move backward for all a[i]<=a[end]
while (i>start && a[i]<=a[end])
i--;
if (i==start)
break;
else {
//a[i]>a[end], compare volumn
int tmp = Math.min(a[i], a[start]) * (i-start);
if ( tmp > maxVolume ) {
maxVolume = tmp;
maxStop = i;
}
end = i; //update stop poniter to i
}
}
}
System.out.println("\nmax volume = " + maxVolume + ", start=" +
maxStart + ", end=" + maxStop);
return maxVolume;
} | g*****i 发帖数: 19 | 39 那不对,给个反例来
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个不对。 : : A[optima_ : A[current_right : the A[ : can
| g***s 发帖数: 3811 | 40 3 5 1 5 3
【在 g*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那不对,给个反例来
| | | B*M 发帖数: 1340 | 41 大家看看这个怎么样?
double maxArea(double a[], int size){
int left = 0;
int right = size - 1;
double area = min(a[left], a[right]) * (right - left);
while(left < right){
double temp = min(a[left], a[right]) * (right - left);
area = temp > area ? temp :area;
if(a[left] < a[right]){
double t = a[left];
while(a[left] <= t && left < right){
left ++;
}
} else {
double t = a [right];
while(a[right] <= t && left < right){
right --;
}
}
}
return area;
}
【在 g***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 3 5 1 5 3
| B*M 发帖数: 1340 | 42 您老这思路和我老是一样的,
a1
).
【在 h*********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 前面有人已经提过了,这提不是那个经典的 histogram题目。 : 你的例子,最大值是16. 就是4和5和x轴形成的容器。
|
|