2636. Promise 对象池 🔒

🟠   🔗 力扣 LeetCode

题目

Given an array of asynchronous functions functions and a pool limit n, return an asynchronous function promisePool. It should return a promise that resolves when all the input functions resolve.

Pool limit is defined as the maximum number promises that can be pending at once. promisePool should begin execution of as many functions as possible and continue executing new functions when old promises resolve. promisePool should execute functions[i] then functions[i + 1] then functions[i + 2], etc. When the last promise resolves, promisePool should also resolve.

For example, if n = 1, promisePool will execute one function at a time in series. However, if n = 2, it first executes two functions. When either of the two functions resolve, a 3rd function should be executed (if available), and so on until there are no functions left to execute.

You can assume all functions never reject. It is acceptable for promisePool to return a promise that resolves any value.

Example 1:

Input: functions = [

() => new Promise(res => setTimeout(res, 300)), () => new Promise(res => setTimeout(res, 400)), () => new Promise(res => setTimeout(res, 200)) ] n = 2

Output: [[300,400,500],500]

Explanation: Three functions are passed in. They sleep for 300ms, 400ms, and 200ms respectively. They resolve at 300ms, 400ms, and 500ms respectively. The returned promise resolves at 500ms.

• At t=0, the first 2 functions are executed. The pool size limit of 2 is reached.
• At t=300, the 1st function resolves, and the 3rd function is executed. Pool size is 2.
• At t=400, the 2nd function resolves. There is nothing left to execute. Pool size is 1.
• At t=500, the 3rd function resolves. Pool size is zero so the returned promise also resolves.

Example 2:

Input: functions = [

() => new Promise(res => setTimeout(res, 300)), () => new Promise(res => setTimeout(res, 400)), () => new Promise(res => setTimeout(res, 200)) ] n = 5

Output: [[300,400,200],400]

Explanation: The three input promises resolve at 300ms, 400ms, and 200ms respectively. The returned promise resolves at 400ms.

• At t=0, all 3 functions are executed. The pool limit of 5 is never met.
• At t=200, the 3rd function resolves. Pool size is 2.
• At t=300, the 1st function resolved. Pool size is 1.
• At t=400, the 2nd function resolves. Pool size is 0, so the returned promise also resolves.

Example 3:

Input: functions = [

() => new Promise(res => setTimeout(res, 300)), () => new Promise(res => setTimeout(res, 400)), () => new Promise(res => setTimeout(res, 200)) ] n = 1

Output: [[300,700,900],900]

Explanation: The three input promises resolve at 300ms, 700ms, and 900ms respectively. The returned promise resolves at 900ms.

• At t=0, the 1st function is executed. Pool size is 1.
• At t=300, the 1st function resolves and the 2nd function is executed. Pool size is 1.
• At t=700, the 2nd function resolves and the 3rd function is executed. Pool size is 1.
• At t=900, the 3rd function resolves. Pool size is 0 so the returned promise resolves.

Constraints:

0 <= functions.length <= 101 <= n <= 10

题目大意

请你编写一个异步函数 promisePool ，它接收一个异步函数数组 functions 和 池限制 n。它应该返回一个 promise 对象，当所有输入函数都执行完毕后，promise 对象就执行完毕。

池限制 定义是一次可以挂起的最多 promise 对象的数量。promisePool 应该开始执行尽可能多的函数，并在旧的 promise 执行完毕后继续执行新函数。promisePool 应该先执行 functions[i]，再执行 functions[i + 1]，然后执行 functions[i + 2]，等等。当最后一个 promise 执行完毕时，promisePool 也应该执行完毕。

例如，如果 n = 1 , promisePool 在序列中每次执行一个函数。然而，如果 n = 2 ，它首先执行两个函数。当两个函数中的任何一个执行完毕后，再执行第三个函数(如果它是可用的)，依此类推，直到没有函数要执行为止。

你可以假设所有的 functions 都不会被拒绝。对于 promisePool 来说，返回一个可以解析任何值的 promise 都是可以接受的。

解题思路

池限制的核心是控制并发数量，即同时只能有最多 n 个异步任务在执行，需要在一个任务执行完后，才能启动新的任务。

1. 定义一个调度器函数executeNext，它会递归地调用自身以确保所有任务按顺序执行。每次执行一个函数后，会继续执行下一个函数，直到函数数组为空。

2. 创建并发池，使用 Array(n).fill(null) 创建一个长度为 n 的数组，map 方法用来调用 executeNext，即启动 n 个并发任务。

3. Promise.all 会等待所有并发任务完成，确保 promisePool 函数在所有任务都执行完后才 resolve。

复杂度分析

• 时间复杂度: O(m)，其中 m 是 functions 的长度。每个任务的执行时间取决于各自的执行时间，总共会执行 m 个任务。
• 空间复杂度: O(n)，因为最多会同时执行 n 个任务。

代码

/**
 * @param {Function[]} functions
 * @param {Number} n
 * @return {Function}
 */
var promisePool = async function (functions, n) {
	const executeNext = async () => {
		if (functions.length === 0) return; // 所有函数都执行完毕
		const fn = functions.shift(); // 取出下一个要执行的函数
		await fn(); // 执行函数并等待其完成
		await executeNext(); // 递归调用，处理下一个任务
	};

	// 创建 n 个并发任务，开始执行
	const pool = Array(n).fill(null).map(executeNext);

	// 等待所有并发任务都完成
	await Promise.all(pool);
};

/**
 * Example usage:
 * const sleep = (time) => new Promise(resolve => setTimeout(resolve, time));
 *
 * promisePool([() => sleep(500), () => sleep(400), () => sleep(300)], 2)
 *   .then(() => console.log('All functions done'));
 */

相关题目

题号	标题	题解	标签	难度
2621	睡眠函数	[✓]
2622	有时间限制的缓存	[✓]
2637	有时间限制的 Promise 对象	[✓]
2676	节流 🔒	[✓]