力扣1700题解题详解：队列模拟与贪心算法的C++实现

19339201706

问题描述与基础分析

力扣1700题描述了一个快餐店的排队场景：学生们按顺序排队购买三明治，而三明治以栈的形式存放。每个学生要么喜欢圆形三明治（值为0），要么喜欢方形三明治（值为1）。当队列最前面的学生遇到喜欢的三明治时，会拿走并离开队列；否则会重新排到队尾。我们需要计算无法吃到午餐的学生数量。这个问题本质上考察的是队列（Queue）和栈（StACk）的配合使用，以及如何通过模拟过程找到最优解。

暴力模拟解法思路

最直观的解法是直接模拟整个排队过程。我们可以使用C++的queue来维护学生队列，用vector或stack来表示三明治栈。算法步骤如下：初始化学生队列和三明治栈，进入循环，每次取出队首学生和栈顶三明治进行比较。如果匹配则两者都移除，计数器归零；否则学生重新入队，不匹配计数器加1。当不匹配次数等于队列长度时，说明剩余学生都无法获得喜欢的三明治，循环终止。这种方法时间复杂度为O(n^2)，在最坏情况下（如所有学生都喜欢同一种三明治）性能较差，但代码直观易于理解。

贪心算法优化策略

仔细观察会发现，其实不需要完整模拟整个过程。关键在于统计喜欢每种三明治的学生数量。我们可以先遍历学生队列，统计喜欢圆形和方形三明治的人数。依次检查三明治栈：对于栈顶的三明治类型，如果还有喜欢它的学生，则该学生得到满足，对应计数减1；否则剩下的学生都无法得到满足。这种方法将时间复杂度优化到O(n)，空间复杂度O(1)，是本题的最优解法。贪心思想在这里体现在我们总是优先处理栈顶的三明治，这是解决问题的关键突破口。

C++代码实现与逐行注释

C++

int countStudents(vector& students, vector& sandwiches) {    int count[2 = {0}; // 统计喜欢0和1的学生数量    for(int s : students) count[s++;        for(int s : sandwiches) {        if(count[s == 0) break; // 没有喜欢当前三明治的学生        count[s--; // 满足一个学生    }        return count[0 + count[1; // 返回无法满足的学生总数}

边界条件与测试用例分析

为了确保代码的健壮性，需要考虑多种边界情况：空输入、所有学生偏好相同、三明治栈全为一种类型等。测试用例1：students = [1,1,0,0], sandwiches = [0,1,0,1]，应该返回0，因为所有学生都能得到满足。测试用例2：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]，应返回3，因为三个喜欢1的学生无法获得三明治。在编写代码时，这些边界条件都需要被充分考虑，这也是力扣题目考察的重要方面。

原文：力扣1700题解题详解：队列模拟与贪心算法的C++实现