Easy

题目描述

学校的自助餐厅在午餐时间提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队伍中，每个学生要么喜欢方形三明治，要么喜欢圆形三明治。

自助餐厅里三明治的数量等于学生的数量。三明治放在一个栈中，在每个步骤中：

  • 如果在队伍最前面的学生喜欢栈顶的三明治，那么会拿走它并离开队伍。
  • 否则，这名学生会放弃这个三明治并回到队伍的末尾。

这个过程会一直持续下去，直到队伍中所有的学生都不愿意拿走栈顶的三明治为止。

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

示例 1：

输入：students = [1,1,0,0], sandwiches = [0,1,0,1]
输出：0
解释：
- 最前面的学生放弃最顶上的三明治，并回到队伍的末尾，学生队伍变为 students = [1,0,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队伍的末尾，学生队伍变为 students = [0,0,1,1]。
- 最前面的学生拿走最顶上的三明治，并离开队伍，学生队伍变为 students = [0,1,1]，三明治栈变为 sandwiches = [1,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队伍的末尾，学生队伍变为 students = [1,1,0]。
- 最前面的学生拿走最顶上的三明治，并离开队伍，学生队伍变为 students = [1,0]，三明治栈变为 sandwiches = [0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队伍的末尾，学生队伍变为 students = [0,1]。
- 最前面的学生拿走最顶上的三明治，并离开队伍，学生队伍变为 students = [1]，三明治栈变为 sandwiches = [1]。
- 最前面的学生拿走最顶上的三明治，并离开队伍，学生队伍变为 students = []，三明治栈变为 sandwiches = []。
因此所有学生都可以吃到午餐。

示例 2：

输入：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
输出：3

提示：

  • 1 <= students.length, sandwiches.length <= 100
  • students.length == sandwiches.length
  • sandwiches[i] 要么是 0，要么是 1
  • students[i] 要么是 0，要么是 1

解题思路

这道题可以用两种解法来解决：

解法一：直接模拟 按照题意直接模拟整个过程，使用队列来表示学生队伍，使用栈来表示三明治。每次检查队首学生是否喜欢栈顶三明治，如果喜欢就都移除，否则学生到队尾。当连续一轮所有学生都不喜欢当前栈顶三明治时，停止模拟。这种方法直观但效率较低。

解法二：计数法（推荐） 观察问题的关键：当某种类型的三明治出现在栈顶时，如果队伍中没有喜欢这种三明治的学生，那么所有剩余学生都无法继续吃到三明治。

因此我们可以统计学生对两种三明治的偏好数量，然后按照三明治栈的顺序来分配。对于每个三明治，如果有对应偏好的学生就分配给他们，否则剩余的所有学生都无法吃到。

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，比直接模拟更高效。

核心思想是：我们不需要关心学生的具体顺序，只需要知道还剩多少个喜欢某种三明治的学生。

代码实现

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int count0 = 0, count1 = 0;
        
        // 统计喜欢每种三明治的学生数量
        for (int student : students) {
            if (student == 0) count0++;
            else count1++;
        }
        
        // 按照三明治栈的顺序分配
        for (int sandwich : sandwiches) {
            if (sandwich == 0) {
                if (count0 > 0) count0--;
                else break; // 没有喜欢圆形三明治的学生了
            } else {
                if (count1 > 0) count1--;
                else break; // 没有喜欢方形三明治的学生了
            }
        }
        
        return count0 + count1;
    }
};

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        count0 = count1 = 0
        
        # 统计喜欢每种三明治的学生数量
        for student in students:
            if student == 0:
                count0 += 1
            else:
                count1 += 1
        
        # 按照三明治栈的顺序分配
        for sandwich in sandwiches:
            if sandwich == 0:
                if count0 > 0:
                    count0 -= 1
                else:
                    break  # 没有喜欢圆形三明治的学生了
            else:
                if count1 > 0:
                    count1 -= 1
                else:
                    break  # 没有喜欢方形三明治的学生了
        
        return count0 + count1

public class Solution {
    public int CountStudents(int[] students, int[] sandwiches) {
        int count0 = 0, count1 = 0;
        
        // 统计喜欢每种三明治的学生数量
        foreach (int student in students) {
            if (student == 0) count0++;
            else count1++;
        }
        
        // 按照三明治栈的顺序分配
        foreach (int sandwich in sandwiches) {
            if (sandwich == 0) {
                if (count0 > 0) count0--;
                else break; // 没有喜欢圆形三明治的学生了
            } else {
                if (count1 > 0) count1--;
                else break; // 没有喜欢方形三明治的学生了
            }
        }
        
        return count0 + count1;
    }
}

var countStudents = function(students, sandwiches) {
    let queue = [...students];
    let stack = [...sandwiches];
    let consecutiveSkips = 0;
    
    while (queue.length > 0 && consecutiveSkips < queue.length) {
        if (queue[0] === stack[0]) {
            queue.shift();
            stack.shift();
            consecutiveSkips = 0;
        } else {
            queue.push(queue.shift());
            consecutiveSkips++;
        }
    }
    
    return queue.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型计数法直接模拟
时间复杂度O(n)O(n²)
空间复杂度O(1)O(n)

其中 n 是学生数量。计数法只需要遍历数组两次，而直接模拟在最坏情况下可能需要 O(n²) 的时间复杂度。

相关题目