-
-
Save happyWinner/9516365012959289bbb4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.HashMap; | |
import java.util.LinkedList; | |
import java.util.List; | |
/** | |
* You have a stack of n boxes, with widths wi, height 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 strictly larger than the box above it in width, height, and depth. | |
* Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box. | |
* | |
* Time Complexity: O(n^2) | |
* Space Complexity: O(n) | |
*/ | |
public class Question9_10 { | |
public LinkedList<Box> maxHeight(Box[] boxes) { | |
if (boxes == null || boxes.length == 0) { | |
return null; | |
} | |
HashMap<Box, LinkedList<Box>> map = new HashMap<Box, LinkedList<Box>>(); | |
return recMaxHeight(boxes, null, map); | |
} | |
private LinkedList<Box> recMaxHeight(Box[] boxes, Box bottom, HashMap<Box, LinkedList<Box>> map) { | |
if (map.containsKey(bottom)) { | |
return new LinkedList<Box>(map.get(bottom)); | |
} | |
LinkedList<Box> maxStack = new LinkedList<Box>(); | |
for (int i = 0; i < boxes.length; ++i) { | |
if (bottom == null || boxes[i].width < bottom.width && boxes[i].depth < bottom.depth) { | |
LinkedList<Box> stack = recMaxHeight(boxes, boxes[i], map); | |
if (stackHeight(maxStack) < stackHeight(stack)) { | |
maxStack = stack; | |
} | |
} | |
} | |
if (bottom != null) { | |
maxStack.addFirst(bottom); | |
map.put(bottom, maxStack); | |
} | |
return maxStack; | |
} | |
private int stackHeight(List<Box> stack) { | |
int height = 0; | |
for (Box box : stack) { | |
height += box.height; | |
} | |
return height; | |
} | |
public static void main(String[] args) { | |
Question9_10 question9_10 = new Question9_10(); | |
Box[] boxes = {new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2),new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3), new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2)}; | |
LinkedList<Box> stack = question9_10.maxHeight(boxes); | |
for (Box box : stack) { | |
System.out.println(box.toString()); | |
} | |
} | |
} | |
class Box { | |
int width; | |
int height; | |
int depth; | |
Box(int width, int height, int depth) { | |
this.width = width; | |
this.height = height; | |
this.depth = depth; | |
} | |
@Override | |
public String toString() { | |
return "width: " + width + ", height: " + height + ", depth: " + depth; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment