题目描述

学校的自助午餐提供圆形和方形的三明治，分别用 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈里，每一轮：

  • 如果队列最前面的学生喜欢栈顶的三明治，会拿走它并离开队列；
  • 否则学生会放弃这个三明治并回到队列的尾部。
    这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。返回无法吃上午餐的学生数量。

例如：students = [1,1,0,0]，sandwiches = [0,1,0,1]，输出 0。

解释：所有学生最终都能拿到喜欢的三明治。

解题思路

核心思想

这是一个模拟问题，使用队列来模拟学生的排队行为。

步骤

  1. 将所有学生放入队列 queue 中。
  2. 遍历三明治栈（sandwiches），对于每个三明治：
    • 记录已检查的学生数 r = 0。
    • 不断检查队首学生是否喜欢当前三明治：
      • 如果喜欢（queue.peek() == sandwich），该学生拿走三明治并出队，跳出内层循环。
      • 如果不喜欢，该学生回到队尾（queue.offer(queue.poll())），r++。
      • 关键：如果 r == queue.size()，说明所有剩余学生都不喜欢当前栈顶三明治，此后的学生都无法吃饭，直接返回 queue.size()。
    • 如果学生喜欢三明治，出队（该学生已吃饭），继续处理下一个三明治。
  3. 返回 queue.size()。

为什么需要内层循环计数 r？

学生在队列中循环，如果一轮遍历完所有学生后仍然没有人喜欢栈顶的三明治，那么之后的循环也无法改变结果（学生不变，三明治不变），因此可以提前终止。

示例说明

以 students = [1,1,0,0]，sandwiches = [0,1,0,1] 为例：

  • 队列：[1,1,0,0]，栈顶三明治=0
  • 队首=1，不喜欢，转到队尾：[1,0,0,1]
  • 队首=1，不喜欢，转到队尾：[0,0,1,1]
  • 队首=0，喜欢！出队，三明治消耗
  • 队列：[0,1,1]，栈顶三明治=1
  • 队首=0，不喜欢，转到队尾：[1,1,0]
  • 队首=1，喜欢！出队
  • 依此类推…最终 queue 为空，返回 0。

复杂度分析

  • 时间复杂度：O(n²)，每个学生可能被反复移到队尾多次。
  • 空间复杂度：O(n)，队列存储所有学生。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package code.J1700;

import java.util.LinkedList;
import java.util.Queue;

public class J1700 {
    public int countStudents(int[] students, int[] sandwiches) {
        Queue<Integer> queue = new LinkedList<>();
        for (int student : students) queue.offer(student);
        for (int sandwich : sandwiches) {
            int r = 0;
            while (!queue.isEmpty() && queue.peek() != sandwich){
                if (r == queue.size()) break;
                queue.offer(queue.poll());
                r++;
            }
            if (!queue.isEmpty() && queue.peek() != sandwich) return queue.size();
            queue.poll();
        }
        return queue.size();
    }
}