Easy

题目描述

有 n 个人在排队买票，其中第 0 个人在队列的最前面，第 (n - 1) 个人在队列的最后面。

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

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

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

示例 1：

输入：tickets = [2,3,2], k = 2
输出：6
解释：
- 第 1 轮，队列中的每个人都买一张票，队列变为 [1,2,1]。
- 第 2 轮，队列中的每个人都买一张票，队列变为 [0,1,0]。
- 第 3 轮，队列中的每个人都买一张票，第 k 个人买完票。

示例 2：

输入：tickets = [5,1,1,1], k = 0
输出：8
解释：
- 第 1 轮，队列中的每个人都买一张票，队列变为 [4,0,0,0]。
- 现在，只有第 0 个人需要继续买票。
- 第 0 个人买了 4 张票，总共花费 8 秒。

提示：

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

解题思路

这道题有两种解法思路：

方法一：队列模拟 最直观的方法是直接模拟购票过程。使用队列存储每个人的信息（包括需要买的票数和原始位置），然后逐秒模拟：每次队首的人买一张票，如果还需要买票就重新入队，直到位置k的人买完所有票为止。

方法二：数学优化（推荐） 观察发现，我们不需要真正模拟整个过程。对于位置k的人要买完tickets[k]张票，我们可以计算：

  • 对于位置在k之前的人：他们最多能买min(tickets[i], tickets[k])张票
  • 对于位置k的人：买tickets[k]张票
  • 对于位置在k之后的人：他们最多能买min(tickets[i], tickets[k]-1)张票（因为当k买完最后一张票时就结束了）

这样直接计算总时间，时间复杂度更优。

代码实现

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int time = 0;
        int target = tickets[k];
        
        for (int i = 0; i < tickets.size(); i++) {
            if (i <= k) {
                // 位置在k之前或就是k的人，最多买min(tickets[i], target)张票
                time += min(tickets[i], target);
            } else {
                // 位置在k之后的人，最多买min(tickets[i], target-1)张票
                time += min(tickets[i], target - 1);
            }
        }
        
        return time;
    }
};

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        time = 0
        target = tickets[k]
        
        for i in range(len(tickets)):
            if i <= k:
                # 位置在k之前或就是k的人，最多买min(tickets[i], target)张票
                time += min(tickets[i], target)
            else:
                # 位置在k之后的人，最多买min(tickets[i], target-1)张票
                time += min(tickets[i], target - 1)
        
        return time

public class Solution {
    public int TimeRequiredToBuy(int[] tickets, int k) {
        int time = 0;
        int target = tickets[k];
        
        for (int i = 0; i < tickets.Length; i++) {
            if (i <= k) {
                // 位置在k之前或就是k的人，最多买min(tickets[i], target)张票
                time += Math.Min(tickets[i], target);
            } else {
                // 位置在k之后的人，最多买min(tickets[i], target-1)张票
                time += Math.Min(tickets[i], target - 1);
            }
        }
        
        return time;
    }
}

/**
 * @param {number[]} tickets
 * @param {number} k
 * @return {number}
 */
var timeRequiredToBuy = function(tickets, k) {
    let time = 0;
    const target = tickets[k];
    
    for (let i = 0; i < tickets.length; i++) {
        if (i <= k) {
            // 位置在k之前或就是k的人，最多买min(tickets[i], target)张票
            time += Math.min(tickets[i], target);
        } else {
            // 位置在k之后的人，最多买min(tickets[i], target-1)张票
            time += Math.min(tickets[i], target - 1);
        }
    }
    
    return time;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型队列模拟数学优化
时间复杂度O(sum(tickets))O(n)
空间复杂度O(n)O(1)

说明：

  • 队列模拟：最坏情况下需要模拟所有人买完所有票的过程
  • 数学优化：只需要遍历一次数组，直接计算结果

相关题目