力扣1700题解题详解：队列模拟与贪心算法的C++实现
问题描述与基础分析
力扣1700题描述了一个快餐店的排队场景：学生们按顺序排队购买三明治，而三明治以栈的形式存放。每个学生要么喜欢圆形三明治（值为0），要么喜欢方形三明治（值为1）。当队列最前面的学生遇到喜欢的三明治时，会拿走并离开队列；否则会重新排到队尾。我们需要计算无法吃到午餐的学生数量。这个问题本质上考察的是队列（Queue）和栈（StACk）的配合使用，以及如何通过模拟过程找到最优解。
暴力模拟解法思路
最直观的解法是直接模拟整个排队过程。我们可以使用C++的queue来维护学生队列，用vector或stack来表示三明治栈。算法步骤如下：初始化学生队列和三明治栈，进入循环，每次取出队首学生和栈顶三明治进行比较。如果匹配则两者都移除，计数器归零；否则学生重新入队，不匹配计数器加1。当不匹配次数等于队列长度时，说明剩余学生都无法获得喜欢的三明治，循环终止。这种方法时间复杂度为O(n^2)，在最坏情况下（如所有学生都喜欢同一种三明治）性能较差，但代码直观易于理解。
仔细观察会发现，其实不需要完整模拟整个过程。关键在于统计喜欢每种三明治的学生数量。我们可以先遍历学生队列，统计喜欢圆形和方形三明治的人数。依次检查三明治栈：对于栈顶的三明治类型，如果还有喜欢它的学生，则该学生得到满足，对应计数减1；否则剩下的学生都无法得到满足。这种方法将时间复杂度优化到O(n)，空间复杂度O(1)，是本题的最优解法。贪心思想在这里体现在我们总是优先处理栈顶的三明治，这是解决问题的关键突破口。
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的学生无法获得三明治。在编写代码时，这些边界条件都需要被充分考虑，这也是力扣题目考察的重要方面。
算法复杂度与优化证明
贪心算法的正确性可以通过数学归纳法证明：假设前k个三明治已经最优分配，那么对于第k+1个三明治，如果还有对应偏好的学生存在，则分配不会影响最终结果；如果没有，则剩余学生确实无法满足。时间复杂度方面，两个独立的O(n)循环使整体保持线性复杂度。空间上只使用了常数大小的额外空间，是典型的原地算法。相比暴力解法，这种优化在n较大时（如1e5数量级）优势明显，这也是力扣题目期望我们达到的算法水平。
通过本文的系统讲解，我们深入剖析了力扣1700题的解题思路，从暴力模拟到贪心优化，最终给出了高效的C++实现。这道题很好地训练了我们对队列和栈的理解，以及如何发现并利用问题特性进行算法优化。掌握这类问题的解决模式，对提升算法思维和编程面试能力都大有裨益。
原创内容 转载请注明出处
