📘 題目敘述
給你一個整數陣列 prices，其中 prices[i] 表示商店中第 i 個商品的價格。
商店有一個特別折扣規則：
如果你買第 i 個商品，你會得到一個折扣，折扣值等於 prices[j]，其中 j 是滿足以下條件的最小 index：
j > iprices[j] <= prices[i]
如果不存在這樣的 j，那這個商品就沒有折扣。
請回傳一個整數陣列 answer，其中 answer[i] 表示第 i 個商品套用折扣後的最終價格。
條件限制
1 <= prices.length <= 5001 <= prices[i] <= 1000
🧠 解題思路
這題如果直接做，會是：
- 對每個位置
i - 往右找第一個
prices[j] <= prices[i]
但這樣會一直重複往右掃。
我這份做法是用 stack 來記：
前面那些還沒找到折扣的商品 index。
當我現在走到一個新價格 np = prices[i] 時，
我就拿它去看 stack 頂端那些商品，能不能把它當成它們的折扣。
如果 stack 頂端那個商品價格 prices[s.top()] >= np，代表：
- 現在這個
np - 就是它右邊第一個小於等於它的價格
所以它的答案就可以直接算成：
prices[s.top()] - np
然後把那個 index 從 stack pop 掉。
如果 stack 頂端那個商品價格比 np 還小，表示：
- 現在這個
np不能當它的折扣 - 而且更早的那些商品也先不用看了
- 所以可以先停下來
等把所有能被 np 折扣的商品都處理完後，再把目前這個 index i push 進 stack，表示：
- 它自己現在也還沒找到折扣
- 要留給之後右邊的價格來處理
最後 stack 裡還剩下的那些 index，代表它們一路看到結尾都沒有找到折扣，所以答案就是原價。
也就是說，這題的核心就是：
用 stack 存前面還沒找到折扣的商品，當新價格出現時，就幫那些價格大於等於它的商品直接結算折扣。
所有變數
n：prices的長度s：stack，存還沒找到折扣的商品 indexans：答案陣列，ans[i]表示第i個商品最後價格np：目前商品價格，也就是prices[i]
🪜 主要流程步驟
1. 先準備答案陣列和 stack
int n = prices.size();
stack<int> s;
vector<int> ans(n);
這裡：
s用來放還沒找到折扣的商品 indexans用來存最後答案
這份寫法不是一開始就把 ans 設成原價，
而是先保留空間，等找到折扣時直接填，最後沒折扣的再補原價。
2. 依序掃過每個商品
for (int i = 0; i < n; i++) {
int np = prices[i];
這裡的 np 就是目前走到的價格。
現在要做的事情是：
- 看這個
np - 能不能成為前面某些商品的折扣
3. 只要 stack 頂端商品價格大於等於目前價格，就幫它結算折扣
題目要找的是：
- 右邊第一個
- 小於等於自己價格的商品
所以如果目前 np 滿足：
prices[s.top()] >= np
那表示對 stack 頂端這個商品來說，現在這個 np 就是它要找的折扣。
因此直接做：
ans[s.top()] = prices[s.top()] - np
然後把這個已經找到折扣的商品從 stack 裡拿掉。
如果 stack 頂端那個商品價格小於 np，那表示：
- 目前這個價格不能折扣它
- 所以先停下來
4. 為什麼這個 np 一定是「第一個」合法折扣
因為我們是從左到右掃描。
某個商品一旦第一次遇到右邊有一個價格 <= 它，
那就是題目要的最小 index j。
而 stack 裡放的就是那些還沒找到折扣的商品，
所以當它第一次被某個 np 結算時，這個 np 自然就是它右邊第一個合法折扣。
5. 把目前商品 index 放進 stack，等之後右邊價格來處理它
s.push(i);
當前面能用 np 結算的商品都處理完後，
就把目前這個商品 i 放進 stack。
表示：
- 它現在還沒找到折扣
- 之後如果右邊出現更小或相等的價格，再來幫它結算
6. 最後還留在 stack 裡的商品都沒有折扣
while (!s.empty()) {
ans[s.top()] = prices[s.top()];
s.pop();
}
如果某個商品一直留到最後都沒被 pop 掉，表示：
- 它右邊根本沒有任何一個價格
<=它
所以它沒有折扣，答案就是原價。
這裡就把它們補成：
ans[index] = prices[index]
7. 最後回傳答案
return ans;
當所有商品都處理完後，ans 就是每個商品套用折扣後的最終價格。
⏱️ 複雜度
設 n = prices.length。
- 時間複雜度：
O(n)每個 index 最多只會被 push 進 stack 一次、pop 出來一次。 - 空間複雜度：
O(n)stack 最壞情況下可能存下所有 index，答案陣列也需要O(n)空間。
💻 程式碼實作
class Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
int n = prices.size();
stack<int> s;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
int np = prices[i];
while (!s.empty()) {
if (prices[s.top()] >= np) {
ans[s.top()] = prices[s.top()] - np;
s.pop();
} else {
break;
}
}
s.push(i);
}
while (!s.empty()) {
ans[s.top()] = prices[s.top()];
s.pop();
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/