05 August 2008
商品折价后的最终价格
给一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果要买第 i 件商品，那么可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，将没有任何折扣。
请返回一个数组，数组中第 i 个元素是折扣后购买商品 i 最终需要支付的价格。
暴力 O(n^2),双重循环，遇到右边第一个跳出循环，没啥好说的
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int[] finalPrices(int[] prices) {
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
if (prices[i] >= prices[j]) {
prices[i] -= prices[j];
break;
}
}
}
return prices;
}
}
单调栈 O(n),维护一个递增的单调栈，栈内元素为数组下标，从栈顶到栈底的下标对应价格严格递减。 入栈时，如果栈不为空，则比较栈顶元素对应的价格和当前的价格如果【当前的价格 ≤ 栈顶的价格】，将栈顶元素移除，并将其对应的价格修改为prices[st.pop()] - prices[i]，重复上述操作直到栈为空或者栈顶元素对应的价格严格小于当前的价格，然后当前的索引 i 进栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int[] finalPrices(int[] prices) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < prices.length; i++) {
while (!stack.isEmpty() && prices[i] <= prices[stack.peek()]) {
int idx = stack.pop();
prices[idx] = prices[idx] - prices[i];
}
stack.push(i);
}
return prices;
}
}