2676. 节流 🔒

🟠   🔗 力扣 LeetCode

题目

Given a function fn and a time in milliseconds t, return a throttled version of that function.

A throttled function is first called without delay and then, for a time interval of t milliseconds, can't be executed but should store the latest function arguments provided to call fn with them after the end of the delay.

For instance, t = 50ms, and the function was called at 30ms, 40ms, and 60ms.

At 30ms, without delay, the throttled function fn should be called with the arguments, and calling the throttled function fn should be blocked for the following t milliseconds.

At 40ms, the function should just save arguments.

At 60ms, arguments should overwrite currently stored arguments from the second call because the second and third calls are made before 80ms. Once the delay has passed, the throttled function fn should be called with the latest arguments provided during the delay period, and it should also create another delay period of 80ms + t.

Throttle Diagram

The above diagram shows how throttle will transform events. Each rectangle represents 100ms and the throttle time is 400ms. Each color represents a different set of inputs.

Example 1:

Input: t = 100, calls = [{"t":20,"inputs":[1]}]

Output: [{"t":20,"inputs":[1]}]

Explanation: The 1st call is always called without delay

Example 2:

Input: t = 50, calls = [ {"t":50,"inputs":[1]}, {"t":75,"inputs":[2]} ]

Output: [{"t":50,"inputs":[1]},{"t":100,"inputs":[2]}]

Explanation:

• The 1st is called a function with arguments (1) without delay.
• The 2nd is called at 75ms, within the delay period because 50ms + 50ms = 100ms, so the next call can be reached at 100ms. Therefore, we save arguments from the 2nd call to use them at the callback of the 1st call.

Example 3:

Input: t = 70, calls = [ {"t":50,"inputs":[1]}, {"t":75,"inputs":[2]}, {"t":90,"inputs":[8]}, {"t": 140, "inputs":[5,7]}, {"t": 300, "inputs": [9,4]} ]

Output: [{"t":50,"inputs":[1]},{"t":120,"inputs":[8]},{"t":190,"inputs":[5,7]},{"t":300,"inputs":[9,4]}]

Explanation:

• The 1st is called a function with arguments (1) without delay.
• The 2nd is called at 75ms within the delay period because 50ms + 70ms = 120ms, so it should only save arguments.
• The 3rd is also called within the delay period, and because we need just the latest function arguments, we overwrite previous ones. After the delay period, we do a callback at 120ms with saved arguments. That callback makes another delay period of 120ms + 70ms = 190ms so that the next function can be called at 190ms.
• The 4th is called at 140ms in the delay period, so it should be called as a callback at 190ms. That will create another delay period of 190ms + 70ms = 260ms.
• The 5th is called at 300ms, but it is after 260ms, so it should be called immediately and should create another delay period of 300ms + 70ms = 370ms.

Constraints:

• 0 <= t <= 1000
• 1 <= calls.length <= 10
• 0 <= calls[i].t <= 1000
• 0 <= calls[i].inputs[j], calls[i].inputs.length <= 10

题目大意

现给定一个函数 fn 和一个以毫秒为单位的时间 t ，请你返回该函数的 节流 版本。

节流 函数首先立即被调用，然后在 t 毫秒的时间间隔内不能再次执行，但应该存储最新的函数参数，以便在延迟结束后使用这些参数调用 fn 。

例如，t = 50ms ，并且函数在 30ms 、 40ms 和 60ms 时被调用。

在 30ms，节流函数 fn 会以这些函数调用，并且对节流函数fn 的调用在接下来的t 毫秒会被阻塞。

在 40ms，函数应当只是存储参数。

在 60ms，参数应该覆盖第二次调用中当前存储的参数，因为第二次和第三次调用是在 80ms 之前进行的。延迟结束后，应该使用延迟期间提供的最新参数来调用 节流 函数 fn，并且它还应该创建另一个 80ms + t 的延迟。

解题思路

这个 throttle 函数的核心思想是通过控制函数的执行频率，防止在短时间内频繁调用同一个函数。通过设置一个延迟时间 t，可以确保在某个时间窗口内，函数只会执行一次。如果在延迟期间再次调用函数，它会保存最新的参数，并在延迟结束后使用这些参数再次执行函数。

1. 初始化变量：

   • pending: 用来标识当前是否有一个正在进行的延迟计时，如果为 true，意味着当前函数调用正在被节流，不允许立即再次调用。
   • nestArgs: 用来存储最新的函数参数，当节流期间再次调用函数时，它会保存最新传递的参数。

2. 立即执行：

   • 在没有延迟的情况下（pending 为 false），立即调用传递的函数 fn(...args)，并将 pending 设为 true，表示此时函数进入节流状态。
   • 设置一个 setTimeout，确保在延迟 t 毫秒后，重置 pending 状态，以允许函数在延迟结束后再次执行。

3. 延迟期间存储最新参数：

   • 当延迟时间内再次调用节流函数时，更新最新的参数到 nestArgs，确保最新的一次调用不会丢失。

4. 延迟结束后执行最新参数：

   • 一旦延迟结束，检查是否存在存储的最新参数。如果存在，则再次递归调用节流函数，使用最新的参数进行调用。

复杂度分析

• 时间复杂度：O(1)，每次调用 throttle 函数的时间复杂度为 O(1)，因为它只是简单的检查计时器和存储参数。
• 空间复杂度：O(1)，主要用于存储最新参数 lastArgs。

代码

/**
 * @param {Function} fn
 * @param {number} t milliseconds
 * @return {Function}
 */
var throttle = function (fn, t) {
	let pending = false,
		nestArgs;
	const throttleFn = function (...args) {
		// 更新最新的参数
		nestArgs = args;
		if (!pending) {
			// 立即调用
			fn(...args);
			pending = true;
			nestArgs = undefined;
			setTimeout(() => {
				pending = false;
				// 在延迟结束后，使用最新参数递归调用节流函数
				if (nestArgs) {
					throttleFn(...nestArgs);
				}
			}, t);
		}
	};
	return throttleFn;
};

/**
 * const throttled = throttle(console.log, 100);
 * throttled("log"); // logged immediately.
 * throttled("log"); // logged at t=100ms.
 */

/**
 * // 测试函数
 * function runTest() {
 * 	const calls = [
 * 		{ t: 50, inputs: [1] },
 * 		{ t: 75, inputs: [2] },
 * 		{ t: 90, inputs: [8] },
 * 		{ t: 140, inputs: [5, 7] },
 * 		{ t: 300, inputs: [9, 4] }
 * 	];
 *
 * 	const results = [];
 * 	const start = performance.now();
 * 	const throttledLog = throttle((...args) => {
 * 		const time = performance.now();
 * 		results.push({ t: Math.floor(time), inputs: args });
 * 		console.log(`Executed at ${time - start}ms with arguments:`, args);
 * 	}, 70);
 *
 * 	calls.forEach((call) => {
 * 		setTimeout(() => {
 * 			throttledLog(...call.inputs);
 * 		}, call.t);
 * 	});
 *
 * 	// 延迟300ms后打印结果
 * 	setTimeout(() => {
 * 		console.log('Final Results:', results);
 * 	}, 400);
 * }
 * runTest();
 */

相关题目

题号	标题	题解	标签	难度
2627	函数防抖	[✓]
2636	Promise 对象池 🔒	[✓]
2637	有时间限制的 Promise 对象	[✓]