→ Rushia: 一眼單調堆疊 然後submit發現比暴力還慢 幹 12/18 19:14
題目:
有一堆商品做成的陣列
你可以拿到折價卷
折價卷可以折的價格是後面的比當前商品價格低的價格
問你折抵完之後大家要花多少錢
思路:
遞增的monotonic stack
看到後面比他小的就pop
然後pop的時候要順便弄價格
0.0
```cpp
class Solution {
public:
vector<int> finalPrices(vector<int>& prices)
{
int n = prices.size();
vector<int> sta;
vector<int> res(n);
for(int i = 0 ; i < n ; i ++)
{
sta.push_back(i);
while(sta.size() > 1 && prices[sta[sta.size()-1]] <= prices[sta[sta.
size()-2]] )
{
int a = sta[sta.size()-2];
int b = sta[sta.size()-1];
res[a] = prices[a] - prices[b];
sta.pop_back();
sta.pop_back();
sta.push_back(b);
}
}
for(int i : sta)
{
res[i] = prices[i];
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.30.88 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734501832.A.489.html