LC.P1488[避免洪水泛滥]

发表于2023-10-13|更新于2023-10-13|LeetCode

|字数总计:138|阅读时长:1分钟|阅读量:

方法一：贪心+哈希表+有序集合

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        TreeSet<Integer> sunny = new TreeSet<>();
        Map<Integer, Integer> rainy = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int k = rains[i];
            if (k > 0) {
                if (rainy.containsKey(k)) {
                    Integer t = sunny.higher(rainy.get(k));
                    if (t == null) return new int[0];
                    ans[t] = k;
                    sunny.remove(t);
                }
                rainy.put(k, i);
            } else {
                sunny.add(i);
                ans[i] = 1;
            }
        }
        return ans;
    }
}