題目描述: 有 n 個人排隊買票,第 i 個人要買 tickets[i] 張票。每個人每次只能買一張,買完後回到隊尾。若某人買完所有需要的票就離開。求第 k 個人買完所有票需要多少秒。
解題思路: 不需要真的模擬排隊過程,可以直接計算每個人對總時間的貢獻。
時間複雜度:O(n) — 遍歷一次陣列即可計算答案。
空間複雜度:O(1) — 只使用常數額外空間。
1. Initialize time = 0. 2. For each person i from 0 to n-1: a. If i <= k: time += min(tickets[i], tickets[k]). b. If i > k: time += min(tickets[i], tickets[k] - 1). 3. Return time.
直接模擬法:使用佇列模擬排隊過程,每次從隊頭取一人、買一張票、若未買完則回到隊尾。當第 k 個人買完時回傳時間。時間複雜度 O(n * max(tickets[i])),對於大量票數時效率低。
分層計算法:按輪次計算,每一輪所有還在隊列中的人各買一張。追蹤每輪離開的人數。本質上等價於上面的 O(n) 解法,但分層思考可能更直觀。