网站实现隶书繁体,宁波做亚马逊网站,要怎么做网站推广,企业宣传片拍摄公司文章目录 题目描述解题思路#xff1a;方法一#xff1a;通俗解法方法二#xff1a;单调栈 leetcode原题链接
1475. 商品折扣后的最终价格 题目描述 给你一个数组 prices #xff0c;其中 prices[i] 是商店里第 i 件商品的价格。 商店里正在进行促销活动#xff0c;如果你… 文章目录 题目描述解题思路方法一通俗解法方法二单调栈 leetcode原题链接
1475. 商品折扣后的最终价格 题目描述 给你一个数组 prices 其中 prices[i] 是商店里第 i 件商品的价格。 商店里正在进行促销活动如果你要买第 i 件商品那么你可以得到与 prices[j] 相等的折扣其中 j 是满足 j i 且 prices[j] prices[i] 的 最小下标 如果没有满足条件的 j 你将没有任何折扣。 请你返回一个数组数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。 提示1
输入prices [8,4,6,2,3]
输出[4,2,4,2,3]
解释
商品 0 的价格为 price[0]8 你将得到 prices[1]4 的折扣所以最终价格为 8 - 4 4 。
商品 1 的价格为 price[1]4 你将得到 prices[3]2 的折扣所以最终价格为 4 - 2 2 。
商品 2 的价格为 price[2]6 你将得到 prices[3]2 的折扣所以最终价格为 6 - 2 4 。
商品 3 和 4 都没有折扣。提示2
输入prices [1,2,3,4,5]
输出[1,2,3,4,5]
解释在这个例子中所有商品都没有折扣。提示3
输入prices [10,1,1,6]
输出[9,0,1,6]提示
1 prices.length 5001 prices[i] 10^3
解题思路
方法一通俗解法
根据题意求出每件商品的折扣然后商品的原价减去折扣即够买价格。
第i件商品的折扣是由第i件商品之后([i1, n))的第一个小于等于prices[i]的商品价格。因此由两层循环可求出每件商品的折扣。
public int[] finalPrices(int[] prices) {int n prices.length;int[] discount new int[n];for (int i 0; i n; i) {discount[i] prices[i];for (int j i 1; j n; j) {if (prices[j] prices[i]) {discount[i] - prices[j];break;}}}return discount;
}方法二单调栈
维护一个元素由栈底到栈顶单调递增的栈。具体地我们遍历元素如果当前元素小于等于栈顶元素栈不为空说明当前元素是栈顶元素的折扣。如下图入栈元素4是栈中6, 8元素的折扣。当遇到小于等于栈顶元素时栈顶元素需要出栈因为要维护栈中元素单调递增。 为了方便栈中元素存储元素的下标。
public int[] finalPrices1(int[] prices) {int n prices.length;StackInteger stack new Stack();int[] discount new int[n];for (int i 0; i n; i) {while (!stack.isEmpty() prices[i] prices[stack.peek()]) {int idx stack.pop();discount[idx] prices[idx] - prices[i];}discount[i] prices[i];stack.push(i);}return discount;
}
