1564. 把箱子放进仓库里 I （贪心）

程序员文章站 2022-03-16 08:25:18

...

LeetCode： 1564. 把箱子放进仓库里 I

题目稍长（因为样例解释的比较详细）

大意就是：给定两个数组，boxes 数组是一组箱子， war 数组是一组房子，现在保持 war 数组顺序不变，可以任意调整 boxes 数组的顺序，最多可以塞进多少个箱子。

其实贪心题里面很多都有思维的参杂。用来帮助贪心

思路：

这里先将 boxes 从小到大排序。
然后对房子数组进行遍历，如果前一个比后一个矮，则后一个更新为前一个矮的。因为当前能通过房子的高度取决于他（本身）与之前的最小高度。
从后往前遍历房子数组，如果 boxes 能放入，就将当前最矮的box 放入，然后指针向后移动下一个 boxes（放入之后最矮的。

贪心

重点第二步的想法


class Solution {

    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        int len = warehouse.length;
        // 从小到大排序
        Arrays.sort(boxes);        

        // 更新 warehouse 高度
        for (int i = 1; i < len; i++) {
            if(warehouse[i] > warehouse[i - 1]){
                warehouse[i] = warehouse[i - 1];
            }
        }

        int ans = 0;
        for (int i = len - 1, j = 0; i >= 0 && j < boxes.length; i--) {
            if(warehouse[i] >= boxes[j]){
                ans++;
                j++;
            }
        }

        return ans;
    }
    
}