Stack of Box


Given a set of boxes, each one has a square bottom and height of 1. Please write a function to return the tallest stack of these boxes. The constraint is that a box can be put on top only when its square bottom is restrictively smaller.




以每个盒子为底都需要遍历一次,时间复杂度 O(n2 ),空间复杂度 O(n)


ArrayList<Box> stackBox(Box boxes[], Box Bottom, HashMap<Box, ArrayList<Box> stackCache){
    int len = boxes.length;
    if (len == 0) return null;
    ArrayList<Box> max_stack;
    int max_height = 0;
    ArrayList<Box> new_stack;
    if (stackCache.contains(bottom)){
        return stackCache.get(bottom);
    } else {
        for (int i = 0; i < len; i++){
            if (boxes[i].canBeAbove(bottom)){
                // solve subproblem
                new_stack = stackBox(boxes, boxes[i], stackCache);
            if (new_stack.size() > max_height){
                max_height = new_stack.length();
                max_stack = new_stack;
    max_stack.insert(0, bottom);
    stackCache.put(bottom, max_stack);
    return max_stack;