g***s
发帖数: 3811 | 1 当年同事去google面试的题目。
给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
（i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
的液体容量最大
(容器不能倾斜)。
大家先做做 | g*********s
发帖数: 1782 | 2 这不就是maximum rectangle in histogram吗。
【在 g***s 的大作中提到】
: 当年同事去google面试的题目。
: 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
: （i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
: 的液体容量最大
: (容器不能倾斜)。
: 大家先做做
| g***s
发帖数: 3811 | 3 haha. 原来是老题。
这题作为acm试题基本就是送分啊
【在 g*********s 的大作中提到】
: 这不就是maximum rectangle in histogram吗。
| g*********s
发帖数: 1782 | 4 对没受过训练的人来说还是有难度。
【在 g***s 的大作中提到】
: haha. 原来是老题。
: 这题作为acm试题基本就是送分啊
| H*M
发帖数: 1268 | 5 it is different
【在 g*********s 的大作中提到】
: 这不就是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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 当年同事去google面试的题目。
: 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
: （i，ai）到（i，０）共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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 都说不是直方柱内接矩形问题了
| g*******y
发帖数: 1930 | 15
有非stack的o(n)方法，我以前没看stack的solution时候想到的，不过现在没太多时间
码字。
大概的基本思路就是，考虑这个问题：现在你要做的是，寻找并记录下：对于直方图的
每一个bar，左边第一个比它更高的
bar的位置 ＋ 右边第一个比它更高的bar的位置。
【在 g***s 的大作中提到】
: 当年同事去google面试的题目。
: 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
: （i，ai）到（i，０）共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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 什么是bar
| | | u******e
发帖数: 758 | 21 could you explan more detail how to solve case
2 1 2
in this problem with stack?
【在 y******5 的大作中提到】
: 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 的大作中提到】
: 还是不太明白
| 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 这不就是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 的大作中提到】
: 当年同事去google面试的题目。
: 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
: （i，ai）到（i，０）共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 的大作中提到】
:
: 我想的一个方法，大家看看。
: 先拿 (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 的大作中提到】
: 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 的大作中提到】
: 前面有人已经提过了，这提不是那个经典的 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 的大作中提到】
: 当年同事去google面试的题目。
: 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
: （i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
: 的液体容量最大
: (容器不能倾斜)。
: 大家先做做
| g***s
发帖数: 3811 | 32 ３１楼和２７楼其实是一个意思。
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 的大作中提到】
: 当年同事去google面试的题目。
: 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
: （i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
: 的液体容量最大
: (容器不能倾斜)。
: 大家先做做
| g***s
发帖数: 3811 | 34 这个不对。
A[optima_
A[current_right
the A[
can
【在 g*****i 的大作中提到】
: 这题和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 的大作中提到】
: ３１楼和２７楼其实是一个意思。
: 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 的大作中提到】
: 这个不对。
:
: A[optima_
: A[current_right
: the A[
: can
| g***s
发帖数: 3811 | 40 3 5 1 5 3
【在 g*****i 的大作中提到】
: 那不对，给个反例来
| | | 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 的大作中提到】
: 3 5 1 5 3
| B*M
发帖数: 1340 | 42 您老这思路和我老是一样的，
a1
).
【在 h*********3 的大作中提到】
: 前面有人已经提过了，这提不是那个经典的 histogram题目。
: 你的例子，最大值是16. 就是4和5和x轴形成的容器。
|
|
