Stack of Boxes: You have a stack of n boxes, with widths wi, heights hi and depths di. The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height, and depth. Implement a method to compute the height of the tallest possible stack. The height of a stack is the sum of the heights of each box.
Hints: #155, #194, #214, #260, #322, #368, #378
解法
先举个例子来解释这个问题，加入有，Box-A(w=1,h=2,d=3)和Box-B(w=1 h=3,d=2)，按照题目中的定义，这两个Box-A和Box-B谁都不比谁大（题目中要求w、h、d都比对方大才算大），但是h的话是Box-B比较大。
要注意的是：
- 如果Box1 > Box2，那么Box1.height 必定 > Box2.height
- 否则，Box1.height 未必 > Box2.height
如果我们把Box排序，那么可能会发现一段连续的Box里的谁都不比谁大，但是它们中肯定存在一个最大的height，比如下面的B1～4都是谁都不比谁大的：
1
2
|
B1(w5,h=5,d=5) B2(w5,h=6,d=5) B3(w5,h=4,d=5) B4(w4,h=7,d=4)
B5(w3,h=3,d=3) B6(w2,h=2,d=2)
|
所以：
1
|
maxHeight(boxes[0~n]) = max(boxes[0~i].height) + maxHeight(boxes[i+1~n])
|
上面的boxes[0~i]指的是在[0, i]范围内的box谁都不比谁大，取这里面的最大height，再加上后面那段里的值。
Box对象：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Box {
int width;
int height;
int depth;
public boolean isLargerThan(Box another) {
return this.width > another.width
&& this.height > another.height
&& this.depth > another.depth;
}
int compareTo(Box another) {
if (this.isLargerThan(another)) {
return -1;
}
if (another.isLargerThan(this)) {
return 1;
}
return another.height - this.height;
}
}
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
public int maxHeight(Box[] boxes) {
Arrays.sort(boxes);
return maxHeight(boxes, 0);
}
public int maxHeight(Box[] boxes, int index) {
if (index == boxes.length) {
return 0;
}
Box curr = boxes[index];
if (index == boxes.length - 1) {
return curr.height;
}
int maxHeight = 0;
// 往后找，找到第一个比当前盒子小的盒子下标i，然后从它开始maxHeight(boxes[i...])
// 结果再加上当前盒子到i之间的盒子的最大height
maxHeight = curr.height;
for (int i = index + 1; i < boxes.length; i++) {
if (!curr.isLargerThan(boxes[i])) {
maxHeight = Math.max(maxHeight, boxes[i].height);
} else {
break;
}
}
maxHeight += maxHeight(boxes, i);
return maxHeight;
}
|
评论