🥪 无法吃午餐的学生数量

📝 题目描述

​ 学校的自助午餐提供圆形和方形的三明治，分别用数字0和1表示。所有学生排成一个队列等待取餐，每个学生要么喜欢圆形的三明治，要么喜欢方形的三明治。

​ 餐厅中三明治的数量与学生的数量始终保持相同，所有三明治都放在一个栈中。学生取三明治时需要遵守以下几点规则。

1. 每一轮只能由队列中的第一个学生取三明治，且必须取栈顶的三明治。
2. 取三明治时，若学生喜欢该三明治，则这名学生会拿走它并离开队列前往就餐，此时进入下一轮取餐。
3. 取三明治时，若学生不喜欢该三明治，则这名学生会放弃它并回到队列的尾部。
4. 当队列中所有的学生都不喜欢栈顶的三明治时，整个取餐过程结束。这意味着队列中剩余的学生都将吃不到午餐。

​ 给定两个整数数组students和sandwiches，其中sandwiches[i]是三明治栈中第$i$个三明治的类型（i = 0是栈的顶部），students[j]是初始学生队列中第$j$名学生对三明治的喜好（j = 0是队列的头部）。请你返回无法吃午餐的学生数量。

🚀 示例

🖊️ 题解

​ 根据题意，栈顶的三明治能否被拿走取决于队列中是否还存在喜欢它的学生，若存在，则这个栈顶的三明治一定会被拿走。因此，学生在队列中的相对位置不影响整个取餐过程，我们只需关心栈顶的三明治最终能否被拿走。

​ 基于此，我们首先可以计算出队列中喜欢吃圆形三明治的学生数量$like0$和喜欢吃方形三明治的学生数量$like1$。其次，对整个取餐过程进行模拟：如果栈顶的元素为0且$like0>0$，则将$like0$减1；如果栈顶的元素为1且$like1>0$，则将$like1$减1；否则终止整个过程，因为对于队列中剩余的学生，栈顶的三明治已经不再被需要。最终，$like0+like1$的值就是无法吃到午餐的学生数量。

public class Solution {
     public int countStudents(int[] students, int[] sandwiches) {
        int like1 = Arrays.stream(students).sum();
        int like0 = students.length - like1;
        for (int i = 0; i < sandwiches.length; i++) {
            int sandwich = sandwiches[i];
            if (sandwich == 0 && like0 > 0) {
                like0--;
            } else if (sandwich == 1 && like1 > 0) {
                like1--;
            } else {
                break;
            }
        }
        return like0 + like1;
    }
}

💭 复杂度分析

​ 基于模拟的解决方案的复杂度分析如下。

• 时间复杂度：$O(n)$，其中$n$为三明治的数量。
• 空间复杂度：$O(1)$。