脚本宝典收集整理的这篇文章主要介绍了[LeetCode] 1475. Final Prices With a Special Discount in a Shop，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

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 <= 500
• 1 <= 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 }

LeetCode 题目总结

脚本宝典总结

以上是脚本宝典为你收集整理的[LeetCode] 1475. Final Prices With a Special Discount in a Shop全部内容，希望文章能够帮你解决[LeetCode] 1475. Final Prices With a Special Discount in a Shop所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。