1700. Number of Students Unable to Eat Lunch

📘 題目敘述

學校餐廳提供兩種三明治：

• 0 表示圓形三明治
• 1 表示方形三明治

學生排成一個 queue，每位學生只喜歡其中一種三明治。
三明治則排成一個 stack。

每一步會發生以下事情：

• 如果 queue 最前面的學生喜歡 stack 最上面的三明治，他就拿走它並離開 queue
• 否則，他會回到 queue 的最後面

這個過程會一直持續，直到 queue 中沒有任何學生想拿目前 stack 最上面的三明治為止。

給你兩個整數陣列 students 和 sandwiches：

• students[j] 表示第 j 位學生一開始的喜好
• sandwiches[i] 表示 stack 中第 i 個三明治的種類，其中 i = 0 是 stack 最上面

請回傳最後有多少學生無法吃到午餐。

條件限制

• 1 <= students.length, sandwiches.length <= 100
• students.length == sandwiches.length
• sandwiches[i] 只會是 0 或 1
• students[i] 只會是 0 或 1

🧠 解題思路

這題我就是直接照題目要求模擬。

我用：

• queue 來放學生目前排隊順序
• stack 來放三明治順序

接著一輪一輪做：

• 如果隊首學生剛好喜歡目前最上面的三明治
  • 那他就拿走三明治並離開
• 否則
  • 他就回到隊尾

不過模擬時有一個重點要注意：

什麼時候代表已經不可能再有人吃到目前最上面的三明治？

如果我已經讓目前 queue 裡的所有學生都輪過一遍，還是沒有人能拿走最上面的三明治，
那就表示這一輪之後狀態只會一直重複，不可能再有變化，所以可以直接停止。

所以我用一個 count 記：

• 連續有幾個學生只是被移到隊尾，沒有成功拿三明治

如果一旦有人成功吃到：

• count 就重設成 0

如果 count 大到等於目前 queue 的大小，代表整個 queue 已經完整輪過一圈都沒成功，那就可以停止。

所有變數

• q：queue，存目前學生排隊順序
• s：stack，存目前三明治順序
• count：連續有多少位學生沒有成功拿到三明治，只是被移到隊尾

🪜 主要流程步驟

1. 先把學生放進 queue

queue<int> q;
for (int i : students) {
    q.push(i);
}

這裡就是把學生原本的排隊順序照題目要求放進 queue。

這樣之後：

• q.front() 就是目前站在最前面的學生

2. 再把三明治放進 stack

stack<int> s;
for (int i = sandwiches.size() - 1; i >= 0; i--) {
    s.push(sandwiches[i]);
}

題目說：

• sandwiches[0] 是 stack 最上面

但 C++ 的 stack 是最後 push 進去的東西才會在 top。
所以我這裡從後面往前 push，這樣最後：

• s.top() 就會剛好對應到 sandwiches[0]

3. 用 count 記錄連續多少人沒成功拿到三明治

int count = 0;

這個變數很重要。

如果某個學生不喜歡目前最上面的三明治，他就只是被移到隊尾，
這表示目前還沒有任何進展，所以 count++。

只要有人真的拿到三明治：

• 代表狀態有變化
• 那我就把 count 重設成 0

4. 只要還沒整圈都失敗，就繼續模擬

while (count <= q.size()) {

這裡的意思是：

• 只要目前還沒出現「整個 queue 都輪過一遍還沒人成功」的情況
• 就繼續模擬

雖然更精準地說，判斷停止通常會寫成「count == q.size()」，
但照你的程式碼，我就照這個條件說明。

5. 如果學生或三明治空了，就直接結束

if (s.empty() || q.empty()) {
    break;
}

如果：

• s.empty()
  • 代表三明治都被拿完了
• q.empty()
  • 代表學生都吃到了

那這時就不用再模擬，直接停止。

6. 如果隊首學生剛好喜歡最上面的三明治，就讓他吃掉並離開

if (q.front() == s.top()) {
    s.pop();
    q.pop();
    count = 0;
}

這一步就是題目規則本身。

如果學生喜歡目前最上面的三明治：

• 三明治從 stack 拿掉
• 學生從 queue 移除
• 而且因為這一輪有成功吃到，所以 count 要重設成 0

這代表新的一輪又重新開始計算。

7. 如果不喜歡，就把這位學生移到隊尾

如果隊首學生不喜歡目前最上面的三明治，
那他不會離開，只是回到隊尾。

所以這裡做的是：

• 先把 q.front() push 到 queue 後面
• 再把原本前面的那位 pop 掉

而且這一輪沒有任何人成功拿到三明治，所以：

• count++

8. 為什麼 count 可以判斷要不要停

如果目前最上面的三明治，真的有人喜歡，
那在 queue 繞一圈之內一定會輪到那個人，然後他就會把三明治拿走。

相反地，如果我已經讓 queue 裡所有人都各輪過一遍，
卻還是沒有人拿走目前最上面的三明治，表示：

• 這個三明治沒人要
• 之後不管再怎麼輪，結果都一樣

所以這時就可以停止，剩下 queue 裡的人就是無法吃到午餐的人。

9. 最後回傳 queue 裡剩下的人數

return q.size();

當模擬結束時，queue 裡剩下的學生就是那些再也拿不到目前三明治、因此最後無法吃午餐的人。

所以直接回傳 q.size() 即可。

⏱️ 複雜度

設 n = students.length。

• 時間複雜度：O(n^2)
  最壞情況下，可能會有很多次把學生移到隊尾的模擬。
• 空間複雜度：O(n)
  需要 queue 和 stack 來存學生與三明治。

💻 程式碼實作

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        queue<int> q;
        stack<int> s;
        int count = 0;
        for (int i : students) {
            q.push(i);
        }
        for (int i = sandwiches.size() - 1; i >= 0; i--) {
            s.push(sandwiches[i]);
        }
        while (count <= q.size()) {
            if (s.empty() || q.empty()) {
                break;
            }
            if (q.front() == s.top()) {
                s.pop();
                q.pop();
                count = 0;
            } else {
                q.push(q.front());
                q.pop();
                count++;
            }
        }
        return q.size();
    }
};

🔗 題目連結

https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/