题目:
有一堆商品做成的阵列
你可以拿到折价卷
折价卷可以折的价格是后面的比当前商品价格低的价格
问你折抵完之后大家要花多少钱
思路:
递增的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;
}
};
```