Given the array prices where prices[i] is the price of the ith item in a shop. There is a special discount for items in the shop, if you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i], otherwise, you will not receive any discount at all.
Return an array where the ith element is the final price you will pay for the ith item of the shop considering the special discount.
Example 1:
Input: prices = [8,4,6,2,3] Output: [4,2,4,2,3] Explanation: For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. For items 3 and 4 you will not receive any discount at all.
Example 2:
Input: prices = [1,2,3,4,5] Output: [1,2,3,4,5] Explanation: In this case, for all items, you will not receive any discount at all.
Example 3:
Input: prices = [10,1,1,6] Output: [9,0,1,6]
Constraints:
1 <= prices.length <= 5001 <= prices[i] <= 10^3
商品折扣后的最终价格。
给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/final-prices-with-a-special-discount-in-a-shop
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题是个简单题，但是做法不止一种。我这里提供两种做法，一种是暴力解，一种是单调栈。
首先是暴力解，对于商品 i 而言，如果他想有 discount，一定要去他的右边找一个满足题意的商品 j，才能 apply j 的 discount，那么我们这里就可以用两层 for 循环解决问题。介于数据规模不是很大，这种做法是不超时的。
时间O(n^2)
空间O(n)
Java实现
1 class Solution { 2 public int[] finalPrices(int[] prices) { 3 int[] res = new int[prices.length]; 4 for (int i = 0; i < prices.length; i++) { 5 int price = prices[i]; 6 res[i] = price; 7 int discount = 0; 8 for (int j = i + 1; j < prices.length; j++) { 9 if (prices[j] <= price) { 10 discount = prices[j]; 11 res[i] = price - discount; 12 break; 13 } 14 } 15 } 16 return res; 17 } 18 }
第二种做法是单调栈，栈中元素是单调递增的。为什么可以用单调栈，首先是因为对于 i 来说，j 一定在他的右边（这里暗示的是所有元素只会被遍历到一次）；另外，我们要找的是第一个遇到的 j，同时 prices[j] <= prices[i]。代码里我是用变量 j 去做 for 循环的，这里我的思路是，对于每一个当前元素 j，我们看是否有可能找到一个对应的 i 满足题意。因为 stack 中，栈顶元素是最后放进去的，所以对于栈顶元素来说，如果当前的 j 能满足 prices[j] <= prices[i]，那么他一定是距离上最接近 i 的。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int[] finalPrices(int[] prices) { 3 int[] res = new int[prices.length]; 4 Stack<Integer> stack = new Stack<>(); 5 for (int j = 0; j < prices.length; j++) { 6 res[j] = prices[j]; 7 while (!stack.isEmpty() && prices[j] <= prices[stack.peek()]) { 8 res[stack.pop()] -= prices[j]; 9 } 10 stack.push(j); 11 } 12 return res; 13 } 14 }