# LEETCODE 1475. Final Prices With a Special Discount in a Shop 解题思路分析

```输入：prices = [8,4,6,2,3]

```输入：prices = [1,2,3,4,5]

```输入：prices = [10,1,1,6]

• `1 <= prices.length <= 500`
• `1 <= prices[i] <= 10^3`

```public int[] finalPrices(int[] prices) {
int[] res = new int[prices.length];
for(int i=0;i<prices.length;i++){
res[i]=prices[i];
for(int j=i+1;j<prices.length;j++){
if(prices[j]<=prices[i]){
res[i]=prices[i]-prices[j];
break;
}
}
}
return res;
}```

Runtime: 2 ms, faster than 62.87% of Java online submissions for Final Prices With a Special Discount in a Shop.

Memory Usage: 41.8 MB, less than 100.00% of Java online submissions for Final Prices With a Special Discount in a Shop.

`[3,4,5,6,7,8,9,10,1]`

`int[] min = [8,8,8,8,8,8,8,8,8]`

```public int[] finalPrices(int[] prices) {
int[] min=new int[prices.length]; // 第一个小于等于自身的下标
min[prices.length-1]=prices.length-1; // 最后一位的min值为自身
for(int i=prices.length-2;i>=0;i--){ // 从倒数第二位向前循环
if(prices[i+1]<=prices[i]){ // 如果后一位小于等于当前数字
min[i]=i+1; // 当前数字的min值为后一位
}else{ // 如果后一位大于当前数字
min[i]=i; // 默认另当前位的min值为自身
int nextMin=i+1; // 后一位下标
while(min[nextMin]!=nextMin){ // 循环找到小于等于当前的数字
nextMin=min[nextMin];
if(prices[nextMin]<=prices[i]){
min[i]=nextMin;
break;
}
}
}
}
int[] res = new int[prices.length]; // 返回结果
for(int i=0;i<min.length;i++){
if(min[i]==i) res[i]=prices[i]; // 没有折扣
else res[i]=prices[i]-prices[min[i]]; // 折扣
}
return res;
}```

Runtime: 1 ms, faster than 99.31% of Java online submissions for Final Prices With a Special Discount in a Shop.

Memory Usage: 39.2 MB, less than 100.00% of Java online submissions for Final Prices With a Special Discount in a Shop.