Leetcode 1564

题意：给定两个数组，boxes记录box的高和warehouse记录warehouse的高，问warehouse中最多放几个box

思路：

1. 把box排序
2. 创建一个stack，从头到尾遍历warehouse
3. 如果stack空，把warehouse[i]的index放进去
4. 如果stack不空且stack顶的高度>warehouse[i]，把warehouse[i]的index放进去
5. 从头到尾遍历box，具体见代码注释

思想：栈

复杂度：时间O（nlgn），空间O（n）

int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
    // 输入参数的null和empty检查，此处忽略了
    Arrays.sort(boxes);
    Stack<Integer> stack = new Stack();
    // 初始化stack
    for(int i=0;i<warehouse.length;i++) {
        if(stack.isEmpty() || warehouse[stack.peek()] > warehouse[i]) {
            stack.add(i);
        }
    }

    int result = 0;
    int pre = warehouse.length;
    for(int i=0;i<boxes.length;i++) {
        // 获取当前stack的顶部值
        int temp = warehouse[stack.peek()];
        // 当前的box的最小高度小于stack的顶部值
        if(boxes[i] <= temp) {
            // 获取可用的warehouse数目
            int cnt = pre - stack.peek();
            // 把符合条件的box放入warehouse
            while(i<boxes.length && boxes[i] <= temp && cnt > 0) {
                result++;
                i++;
                cnt--;
            }
            i--;        
        }
        // 更新pre
        pre = stack.pop();
    }
    return result;
}