【每日算法Day 94】分发糖果

这道题是今天奇安信笔试的第二题，改了下题目场景，将分糖果改成了拆迁分房子，可以使用贪心策略来处理。

LeetCode 135. 分发糖果 (opens new window)

题目描述

有一条街道住户彼此相邻，每家的人数存储在数组中。现在需要要拆迁并为每家住户分若干套新房子，分配规则如下：

• 每户至少分配一套房子。
• 对于相邻的两户，人数多的家庭分到的房子套数要比人数少的家庭分得多。
• 人数相同的家庭房子数目可以不同，不论是否相邻。

请求出总共最少要分配多少套房子。

示例

输入：[4,1,3]
输出：5
解释：这三家分的房子数目为[2,1,2]

输入: [1,2,2]
输出: 4
解释：这三家分的房子数目为[1,2,1]

解题思路

根据贪心选择的策略，对于当前还没有分房子的人家，我们一定是从人口最少的人家开始分房子，那么可以使用堆来辅助得到这个值（也可以使用一个新数组排序并手动去重）。 接下来，我们找到所有人数等于当前待处理最小值的人家，根据其左右两家的情况为其赋值：

1. 如果左右两侧人家的人口都大于等于当前人家的人口，那么可以放心地为当前人家分1套房；
2. 只要发现两侧至少有1家人口比当前人家少（已经分过房子了），那么当前人家应该分的房子数量就是两侧人家分到房子数量的最大值max+1。（人口更多的人家还没处理值为0，不会对max产生影响）

最终统计每家分得的房子数量即可。

public int house (int[] person) {
    // write code here
    //使用堆来按人口从小到大处理
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : person) {
        if (!heap.contains(num))
            heap.offer(num);
    }
    int n = person.length;
    //每家最终要分的房子数量，初始为0
    int[] house = new int[n];
    while (!heap.isEmpty()) {
        int curMin = heap.poll();
        for (int i = 0; i < n; i++) {
            //找到当前要处理的人家，比其人口更少的人家的房子已经分配完毕
            if (person[i] == curMin) {
                //如果左右两侧的数都大于等于当前的数，那么可以放心的设为1
                if ((i == 0 || person[i - 1] >= person[i]) && (i == n - 1 || person[i + 1] >= person[i])) {
                    house[i] = 1;
                } else { //只要有一侧的人口小于当前的人口，那么分配的房子数量就是两侧人口小于当前人家的人家分到房子数量的最大值+1
                    int leftHouse = i == 0 ? 0 : house[i - 1], rightHouse = i == n - 1 ? 0 : house[i + 1];
                    house[i] = Math.max(leftHouse, rightHouse) + 1;
                }
            }
        }
    }
    int total = 0;
    for (int num : house)
        total += num;
    return total;
}