LeetCode 1488. 避免洪水泛滥

Categories:

题目描述
思路分析
1. 解法一：哈希 + 有序集合（推荐）
相似题目

题目描述

✅ 1488. 避免洪水泛滥

思路分析

解法一：哈希 + 有序集合（推荐）

核心思路：

记录每个湖泊上次下雨的时间。

用有序集合保存可抽水的晴天索引，选择最早且在上次下雨之后的晴天。

若找不到合适晴天则无法避免洪水。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示天数。

空间复杂度：O(n)，用于哈希与集合。

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] res = new int[n];
        Map<Integer, Integer> last = new HashMap<>();
        TreeSet<Integer> dryDays = new TreeSet<>();

        for (int i = 0; i < n; i++) {
            if (rains[i] == 0) {
                dryDays.add(i);
                res[i] = 1;
            } else {
                int lake = rains[i];
                res[i] = -1;
                if (last.containsKey(lake)) {
                    Integer dry = dryDays.higher(last.get(lake));
                    if (dry == null) {
                        return new int[0];
                    }
                    res[dry] = lake;
                    dryDays.remove(dry);
                }
                last.put(lake, i);
            }
        }

        return res;
    }
}

func avoidFlood(rains []int) []int {
	n := len(rains)
	res := make([]int, n)

	last := make(map[int]int)
	tree := newTreap()

	for i := 0; i < n; i++ {
		if rains[i] == 0 {
			res[i] = 1
			tree.insert(i)
			continue
		}

		lake := rains[i]
		res[i] = -1
		if prev, ok := last[lake]; ok {
			dry := tree.lowerBound(prev + 1)
			if dry == -1 {
				return []int{}
			}
			res[dry] = lake
			tree.erase(dry)
		}
		last[lake] = i
	}

	return res
}

type treapNode struct {
	key      int
	priority uint32
	left     *treapNode
	right    *treapNode
}

type treap struct {
	root *treapNode
	seed uint32
}

func newTreap() *treap {
	return &treap{seed: 2463534242}
}

func (t *treap) nextPriority() uint32 {
	t.seed ^= t.seed << 13
	t.seed ^= t.seed >> 17
	t.seed ^= t.seed << 5
	return t.seed
}

func rotateRight(y *treapNode) *treapNode {
	x := y.left
	y.left = x.right
	x.right = y
	return x
}

func rotateLeft(x *treapNode) *treapNode {
	y := x.right
	x.right = y.left
	y.left = x
	return y
}

func (t *treap) insert(key int) {
	t.root = t.insertNode(t.root, key)
}

func (t *treap) insertNode(root *treapNode, key int) *treapNode {
	if root == nil {
		return &treapNode{key: key, priority: t.nextPriority()}
	}
	if key < root.key {
		root.left = t.insertNode(root.left, key)
		if root.left.priority > root.priority {
			root = rotateRight(root)
		}
	} else if key > root.key {
		root.right = t.insertNode(root.right, key)
		if root.right.priority > root.priority {
			root = rotateLeft(root)
		}
	}
	return root
}

func (t *treap) erase(key int) {
	t.root = t.eraseNode(t.root, key)
}

func (t *treap) eraseNode(root *treapNode, key int) *treapNode {
	if root == nil {
		return nil
	}
	if key < root.key {
		root.left = t.eraseNode(root.left, key)
	} else if key > root.key {
		root.right = t.eraseNode(root.right, key)
	} else {
		if root.left == nil {
			return root.right
		}
		if root.right == nil {
			return root.left
		}
		if root.left.priority > root.right.priority {
			root = rotateRight(root)
			root.right = t.eraseNode(root.right, key)
		} else {
			root = rotateLeft(root)
			root.left = t.eraseNode(root.left, key)
		}
	}
	return root
}

func (t *treap) lowerBound(key int) int {
	cur := t.root
	ans := -1
	for cur != nil {
		if key <= cur.key {
			ans = cur.key
			cur = cur.left
		} else {
			cur = cur.right
		}
	}
	return ans
}

相似题目

题目	难度	考察点
1488. 避免洪水泛滥	中等	贪心、有序集合
1353. 最多可以参加的会议数目	中等	贪心
1094. 拼车	中等	差分数组
621. 任务调度器	中等	贪心
253. 会议室 II	中等	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/47739821