在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天给一个新的人分享秘密。同时给你一个整数
forget ，表示每个人在发现秘密 forget 天之后会忘记这个秘密。一个人不能
在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 109 + 7 取余后返回。

示例 1：

**输入：** n = 6, delay = 2, forget = 4
**输出：** 5
**解释：**
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

示例 2：

**输入：** n = 4, delay = 1, forget = 3
**输出：** 6
**解释：**
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

提示：

2 <= n <= 1000
1 <= delay < forget <= n

Problem: 2327. 知道秘密的人数

[TOC]

思路

双队列模拟，详情看注释

Code

[]
class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        // delay 队列保存的是知道故事但是还不能分享的人，f队列保存的是知道故事（不管能不能分享，要忘记的人）
        Queue<Integer> d = new LinkedList<>(), f = new LinkedList<>();
        // 第一天一个人知道秘密
        d.offer(1);
        f.offer(1);

        // 可以分享的人树目
        int sharing = 0;

        int m = 1000000007;

        // 以下循环从第二天开始，前半部分处理前一天的情况，后半部分加入今天可以分享人的情况
        for (int i = 2; i <= n; i++) {
            // 处理前一天之后，对今天能分享人的影响
            if (d.size() >= delay) {
                // 如果能分享，要添加至能分享的人，同时移出delay队列
                sharing = (sharing + d.poll()) % m;
            }

            if (f.size() >= forget) {
                // 如果忘记，要移出忘记队列，并且sharing的人数要减少，因为部分人已经不能分享
                sharing = (sharing - f.poll() + m) % m;
            }

            // 可分享人加入队列，准备给明天处理。
            // share 为 0 时，可以充当占位符号，来计时
            f.offer(sharing);
            d.offer(sharing);
        }

        // 最后的结果 d 队列的值 + sharing的值
        int res = sharing;
        while (!d.isEmpty()) {
            res = (res + d.poll()) % m;
        }

        return res;
    }
}

2327-知道秘密的人数

思路

Code