2073. 买票需要的时间

🟢 🔖 队列 数组 模拟 🔗 力扣open in new window LeetCodeopen in new window

题目

There are n people in a line queuing to buy tickets, where the 0th person is at the front of the line and the (n - 1)th person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the ith person would like to buy is tickets[i].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person initially at position k (0-indexed) to finish buying tickets.

Example 1:

Input: tickets = [2,3,2], k = 2

Output: 6

Explanation:

The queue starts as [2,3,2], where the kth person is underlined.
After the person at the front has bought a ticket, the queue becomes [3,2 ,1] at 1 second.
Continuing this process, the queue becomes [2 ,1,2] at 2 seconds.
Continuing this process, the queue becomes [1,2,1] at 3 seconds.
Continuing this process, the queue becomes [2,1] at 4 seconds. Note: the person at the front left the queue.
Continuing this process, the queue becomes [1 ,1] at 5 seconds.
Continuing this process, the queue becomes [1] at 6 seconds. The kth person has bought all their tickets, so return 6.

Example 2:

Input: tickets = [5,1,1,1], k = 0

Output: 8

Explanation:

The queue starts as [5 ,1,1,1], where the kth person is underlined.
After the person at the front has bought a ticket, the queue becomes [1,1,1,4] at 1 second.
Continuing this process for 3 seconds, the queue becomes [4] at 4 seconds.
Continuing this process for 4 seconds, the queue becomes [] at 8 seconds. The kth person has bought all their tickets, so return 8.

Constraints:

n == tickets.length
1 <= n <= 100
1 <= tickets[i] <= 100
0 <= k < n

题目大意

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到队尾重新排队（瞬间发生，不计时间）。如果一个人没有剩下需要买的票，那他将会离开队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

示例 1：

输入： tickets = [2,3,2], k = 2

输出： 6

解释：

队伍一开始为 [2,3,2]，第 k 个人以下划线标识。
在最前面的人买完票后，队伍在第 1 秒变成 [3,2 ,1]。
继续这个过程，队伍在第 2 秒变为[2 ,1,2]。
继续这个过程，队伍在第 3 秒变为[1,2,1]。
继续这个过程，队伍在第 4 秒变为[2,1]。
继续这个过程，队伍在第 5 秒变为[1 ,1]。
继续这个过程，队伍在第 6 秒变为[1]。第 k 个人完成买票，所以返回 6。

示例 2：

输入： tickets = [5,1,1,1], k = 0

输出： 8

解释：

队伍一开始为 [5 ,1,1,1]，第 k 个人以下划线标识。
在最前面的人买完票后，队伍在第 1 秒变成 [1,1,1,4]。
继续这个过程 3 秒，队伍在第 4 秒变为[4]。
继续这个过程 4 秒，队伍在第 8 秒变为[]。第 k 个人完成买票，所以返回 8。

提示：

n == tickets.length
1 <= n <= 100
1 <= tickets[i] <= 100
0 <= k < n

解题思路

初始化一个变量 res，用于累积所需的时间。
遍历队列，计算每个人对总时间的贡献：
- 前半段：对于索引 i ≤ k 的人，他们会至少购买 Math.min(tickets[i], tickets[k]) 张票。
- 后半段：对于索引 i > k 的人，他们最多会购买 Math.min(tickets[i], tickets[k] - 1) 张票，因为在 k 的票买完之后，后续的人不会再购买。
累加所有人的贡献，返回结果 res。

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度，遍历数组一次。
空间复杂度：O(1)，只使用了常量级别的变量。

代码

/**
 * @param {number[]} tickets
 * @param {number} k
 * @return {number}
 */
var timeRequiredToBuy = function (tickets, k) {
	let res = 0;

	for (let i = 0; i < tickets.length; i++) {
		if (i <= k) {
			res += Math.min(tickets[i], tickets[k]); // 当前人最多买到 tickets[k] 张票
		} else {
			res += Math.min(tickets[i], tickets[k] - 1); // 后续人最多买到 tickets[k] - 1 张票
		}
	}

	return res;
};

2073. 买票需要的时间

# 2073. 买票需要的时间

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

2073. 买票需要的时间

题目

题目大意

解题思路

复杂度分析

代码

相关题目