单调栈
#算法
单调栈主要用于线性寻找某个元素后面或前面第一个比它大或者比它小的元素(朴素算法是O(N^2))
class Solution {
public:
vector<int> finalPrices(vector<int>& nums) {
int n = nums.size();
vector<int>ans = nums, s;
for (int i = n - 1;i >= 0;i--) {
//单调栈核心：如果我比你小（或大）而且比你近，你就出栈
while (s.size() && nums[s.back()] > nums[i])s.pop_back();
//这样s.back()一定是最接近的而且比当前元素小(或大)的元素
if (s.size())ans[i] -= nums[s.back()];
s.push_back(i);
}
return ans;
}
};