Medium

题目描述

你的国家有 10^9 个湖泊。最初，所有湖泊都是空的，但当第 n 个湖泊下雨时，第 n 个湖泊就会变满。如果在一个已经满水的湖泊上下雨，就会发生洪水。你的目标是避免任何湖泊发生洪水。

给你一个整数数组 rains，其中：

  • rains[i] > 0 表示第 i 天在 rains[i] 湖泊上下雨
  • rains[i] == 0 表示第 i 天没有下雨，你必须选择一个湖泊并将其抽干

返回一个数组 ans，其中：

  • ans.length == rains.length
  • 如果 rains[i] > 0，则 ans[i] == -1
  • 如果 rains[i] == 0，则 ans[i] 是第 i 天你选择抽干的湖泊

如果有多个有效答案，返回其中任何一个。如果无法避免洪水，返回空数组。

注意，如果你选择抽干一个满的湖泊，它会变空；但如果你选择抽干一个空的湖泊，什么都不会改变。

示例 1:

输入: rains = [1,2,3,4]
输出: [-1,-1,-1,-1]
解释: 第一天后满湖泊为 [1]
第二天后满湖泊为 [1,2]
第三天后满湖泊为 [1,2,3]
第四天后满湖泊为 [1,2,3,4]
没有天可以抽干任何湖泊，且没有湖泊发生洪水。

示例 2:

输入: rains = [1,2,0,0,2,1]
输出: [-1,-1,2,1,-1,-1]
解释: 第一天后满湖泊为 [1]
第二天后满湖泊为 [1,2]
第三天，我们抽干湖泊 2。满湖泊为 [1]
第四天，我们抽干湖泊 1。没有满湖泊。
第五天，满湖泊为 [2]。
第六天，满湖泊为 [1,2]。

示例 3:

输入: rains = [1,2,0,1,2]
输出: []
解释: 第二天后，满湖泊为 [1,2]。我们必须在第三天抽干一个湖泊。
之后，湖泊 [1,2] 会下雨。无论第三天选择抽干哪个湖泊，另一个都会发生洪水。

约束条件:

  • 1 <= rains.length <= 10^5
  • 0 <= rains[i] <= 10^9

解题思路

这是一个贪心策略问题，核心思想是提前规划抽干湖泊的时机。

思路分析：

  1. 数据结构准备：

    • 使用哈希表 lastRain 记录每个湖泊最近一次下雨的天数
    • 使用集合 dryDays 保存可用的抽干天数（rains[i] == 0 的天）
    • 使用结果数组 ans 记录每天的操作

  2. 核心策略：

    • 当某一天下雨时（rains[i] > 0），检查该湖泊是否已经满了
    • 如果湖泊已满，需要在之前的某个抽干日将其抽干
    • 关键是选择最早的、且在该湖泊上次下雨之后的抽干日

  3. 贪心选择：

    • 对于每个需要抽干的湖泊，选择最早可用的抽干日
    • 这样可以为后续可能的冲突保留更多选择

  4. 实现细节：

    • 遍历数组，遇到下雨日检查冲突并分配抽干日
    • 遇到抽干日先加入可用集合，后续分配时再移除
    • 如果无法找到合适的抽干日，返回空数组

算法流程：

  1. 初始化数据结构
  2. 遍历每一天的天气情况
  3. 处理下雨日：检查冲突并分配抽干任务
  4. 处理抽干日：加入可用天数集合
  5. 为未分配的抽干日随意分配湖泊（选1）

代码实现

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> ans(n);
        unordered_map<int, int> lastRain; // 湖泊 -> 最近下雨的天数
        set<int> dryDays; // 可用的抽干天数
        
        for (int i = 0; i < n; i++) {
            if (rains[i] > 0) {
                // 下雨天
                ans[i] = -1;
                if (lastRain.count(rains[i])) {
                    // 湖泊已满，需要找到一个抽干日
                    int lastDay = lastRain[rains[i]];
                    auto it = dryDays.upper_bound(lastDay);
                    if (it == dryDays.end()) {
                        return {}; // 无法避免洪水
                    }
                    ans[*it] = rains[i]; // 在该天抽干这个湖泊
                    dryDays.erase(it);
                }
                lastRain[rains[i]] = i;
            } else {
                // 抽干天
                dryDays.insert(i);
            }
        }
        
        // 为剩余的抽干天随意分配湖泊
        for (int day : dryDays) {
            ans[day] = 1;
        }
        
        return ans;
    }
};

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        ans = [0] * n
        last_rain = {}  # 湖泊 -> 最近下雨的天数
        dry_days = set()  # 可用的抽干天数
        
        for i in range(n):
            if rains[i] > 0:
                # 下雨天
                ans[i] = -1
                if rains[i] in last_rain:
                    # 湖泊已满，需要找到一个抽干日
                    last_day = last_rain[rains[i]]
                    # 找到第一个大于last_day的抽干日
                    available = [day for day in dry_days if day > last_day]
                    if not available:
                        return []  # 无法避免洪水
                    dry_day = min(available)
                    ans[dry_day] = rains[i]  # 在该天抽干这个湖泊
                    dry_days.remove(dry_day)
                last_rain[rains[i]] = i
            else:
                # 抽干天
                dry_days.add(i)
        
        # 为剩余的抽干天随意分配湖泊
        for day in dry_days:
            ans[day] = 1
            
        return ans

public class Solution {
    public int[] AvoidFlood(int[] rains) {
        int n = rains.Length;
        int[] ans = new int[n];
        Dictionary<int, int> lastRain = new Dictionary<int, int>(); // 湖泊 -> 最近下雨的天数
        SortedSet<int> dryDays = new SortedSet<int>(); // 可用的抽干天数
        
        for (int i = 0; i < n; i++) {
            if (rains[i] > 0) {
                // 下雨天
                ans[i] = -1;
                if (lastRain.ContainsKey(rains[i])) {
                    // 湖泊已满，需要找到一个抽干日
                    int lastDay = lastRain[rains[i]];
                    var availableDays = dryDays.GetViewBetween(lastDay + 1, int.MaxValue);
                    if (availableDays.Count == 0) {
                        return new int[0]; // 无法避免洪水
                    }
                    int dryDay = availableDays.Min;
                    ans[dryDay] = rains[i]; // 在该天抽干这个湖泊
                    dryDays.Remove(dryDay);
                }
                lastRain[rains[i]] = i;
            } else {
                // 抽干天
                dryDays.Add(i);
            }
        }
        
        // 为剩余的抽干天随意分配湖泊
        foreach (int day in dryDays) {
            ans[day] = 1;
        }
        
        return ans;
    }
}

var avoidFlood = function(rains) {
    const result = new Array(rains.length);
    const fullLakes = new Set();
    const dryDays = [];
    
    for (let i = 0; i < rains.length; i++) {
        if (rains[i] === 0) {
            dryDays.push(i);
            result[i] = 1;
        } else {
            if (fullLakes.has(rains[i])) {
                let dryDayIndex = -1;
                for (let j = 0; j < dryDays.length; j++) {
                    if (dryDays[j] > -1) {
                        dryDayIndex = j;
                        break;
                    }
                }
                
                if (dryDayIndex === -1) {
                    return [];
                }
                
                const dayToDry = dryDays[dryDayIndex];
                result[dayToDry] = rains[i];
                dryDays[dryDayIndex] = -1;
                fullLakes.delete(rains[i]);
            }
            
            fullLakes.add(rains[i]);
            result[i] = -1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型C++PythonC#JavaScript
时间复杂度O(n log n)O(n²)O(n log n)O(n²)
空间复杂度O(n)O(n)O(n)O(n)

说明：

  • C++ 和 C# 使用了有序集合，查找操作为 O(log n)
  • Python 和 JavaScript 版本中查找最小可用天数需要遍历集合，为 O(n)
  • 总体时间复杂度主要由查找操作决定
  • 空间复杂度主要用于存储湖泊状态和可用抽干天数