[LeetCode] 1700. Number of Students Unable to Eat Lunch

The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:
If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
Otherwise, they will leave it and go to the queue’s end.
This continues until none of the queue students want to take the top sandwich and are thus unable to eat.

You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the i​​​​​​th sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the j​​​​​​th student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

Example 1:
Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0
Explanation:

• Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
• Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
• Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
• Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
• Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
• Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
• Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
• Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
  Hence all students are able to eat.

Example 2:
Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3

Constraints:
1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i] is 0 or 1.
students[i] is 0 or 1.

无法吃午餐的学生数量。

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

如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
否则，这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题 tag 是简单题，但是不小心就容易想复杂了，值得思考。

题意不难理解，students 数组给了每个学生的需求，sandwiches 数组也给了不同 sandwiches 的数量。如果按照题意的描述，可能我们需要一个队列来存储还未吃上饭的同学和一个栈来存储还未被分发出去的三明治。

这里我们做进一步思考，注意到如果栈顶的三明治没有被当前学生拿走，学生可以到队尾，但是三明治不能动，需要看下一个学生是否需要当前这个类型的三明治。我们可以用一个 count 数组统计一下需要圆形 0 和方形 1 的三明治各有几个人。接着我们遍历三明治数组，如果当前的三明治依然有人需要，那么我们就把对应的需求 - 1；如果当前这个三明治没有人要，我们直接就可以返回了，因为学生再绕多少圈，当前这个三明治都无法被拿走。

复杂度

时间O(n)
空间O(1) - 数组长度只有2，可以忽略不计

代码

Java实现

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int circular = 0;
        for (int student : students) {
            if (student == 0) {
                circular++;
            }
        }
        int square = students.length - circular;

        for (int i = 0; i < sandwiches.length; i++) {
            int cur = sandwiches[i];
            if (cur == 0 && circular > 0) {
                circular--;
            } else if (cur == 1 && square > 0) {
                square--;
            } else {
                break;
            }
        }
        return circular + square;
    }
}