What is the best approach to solve Time Needed to Buy Tickets efficiently?

Simulate the queue or use single-pass counting with the minimum of each person's tickets and the target's tickets, following the queue-driven pattern.

Can this problem be solved without explicitly rotating the array?

Yes, by summing contributions per person based on remaining tickets relative to the target index, you can avoid full simulation.

How do you handle people behind the target in the queue?

Only count their turns if they have tickets remaining when the target person has not finished buying all tickets.

What is the time and space complexity of this approach?

Time complexity is O(n) and space complexity is O(1), since we only use counters and no extra arrays or queues.

Why is this problem considered a queue-driven state processing pattern?

Because each person’s position and ticket count directly determine the sequence of actions, mirroring real queue movement and state changes.

#2073

Easy

auto_awesome队列·driven·状态·processing

LeetCode 题解工作台

买票需要的时间

有 n 个人前来排队买票，其中第 0 人站在队伍最前方，第 (n - 1) 人站在队伍最后方。给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。每个人买票都需要用掉恰好 1 秒。一个人一次只能买一张票，…

数组队列模拟

题目描述

有 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

lightbulb

解题思路

方法一：一次遍历

根据题目描述，当第 $k$ 个人完成购票时，在第 $k$ 个人前面的所有人，购买的票数都不会超过第 $k$ 个人购买的票数，而在第 $k$ 个人后面的所有人，购买的票数都不会超过第 $k$ 个人购买的票数减 $1$ 。

因此，我们可以遍历整个队伍，对于第 $i$ 个人，如果 $i \leq k$ ，购票时间为 $\min(\textit{tickets}[i], \textit{tickets}[k])$ ，否则购票时间为 $\min(\textit{tickets}[i], \textit{tickets}[k] - 1)$ 。我们将所有人的购票时间相加即可。

时间复杂度 $O(n)$ ，其中 $n$ 为队伍的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        ans = 0
        for i, x in enumerate(tickets):
            ans += min(x, tickets[k] if i <= k else tickets[k] - 1)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because each person is processed once per effective ticket purchase up to the target's completion. Space complexity is O(1) since only counters are maintained, not a full queue.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Ask if you can avoid simulating the entire queue each second.
question_mark
Check if you understand how returning to the end of the line affects total time.
question_mark
Notice opportunities to optimize using comparisons with the target person's tickets.

warning

常见陷阱

外企场景

error
Forgetting that each person buys only one ticket per turn and must rejoin the line.
error
Counting extra seconds after the target person has finished buying all tickets.
error
Misindexing when calculating time for people behind the target in the queue.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the queue to allow multiple tickets per second and compute total time accordingly.
arrow_right_alt
Consider dynamic arrival where new people join the line, affecting queue-driven timing.
arrow_right_alt
Modify the problem to find total time for multiple target indices simultaneously.

help

常见问题

外企场景

继续练习

#1823 找出游戏的获胜者 #1700 无法吃午餐的学生数量 #2071 你可以安排的最多任务数目