1.问题

You are given an integer 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 integer array answer where answer[i] 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] <= 1000

2. 解题思路

方法1：

1.两个嵌套的for循环来遍历prices数组中的所有元素。第一个循环迭代数组中的每个元素i，而第二个循环则迭代数组中i后面的所有元素j。
2.在内部循环中，如果发现价格比当前价格更低，则使用当前价格减去找到的价格，并将其存储在结果数组result中的当前索引i处。
3.然后使用break语句跳出循环，因为已经找到了当前价格下的最低价格。
4.如果没有找到更低的价格，则将当前价格存储在结果数组的当前索引i处。
5.最后，该方法返回结果数组result。

方法2：

1.定义一个名为stack的栈对象，其元素类型为Integer。
2.使用for循环遍历prices数组中的每个元素i。
3.如果栈不为空且栈顶元素对应的价格大于等于当前元素的价格，则说明当前元素可以作为栈顶元素之前的某个元素的最低价格，并且可以将栈顶元素出栈并且更新栈顶元素对应的价格。在这种情况下，继续判断栈顶元素是否大于等于当前元素的价格，直到栈为空或栈顶元素对应的价格小于当前元素的价格。最后，将当前元素下标加入栈中。
4.将当前元素下标加入栈中。
5.返回更新后的prices数组作为结果。

3. 代码

代码1：

class Solution {
    public int[] finalPrices(int[] prices) {
        int[] result = new int[prices.length];//1.新建数组result
        for (int i = 0; i < prices.length; i++) {
    //2.2个for循环遍历数组，如果满足j>i&&prices[j] <= prices[i]，result[i]=prices[i]-prices[j];否者 result[i]=prices[i];
            for(int j=0;j<prices.length;j++){
                if(j>i&&prices[j] <= prices[i]){
                    result[i]=prices[i]-prices[j];
                    break;
                }else{
                    result[i]=prices[i];
                }
            }
        }
        return  result;//3.返回result
    }
}

代码2：

class Solution {
    public int[] finalPrices(int[] prices) {
        Stack<Integer> stack = new Stack<>(); //1.定义一个栈stack
        for (int i = 0; i < prices.length; i++) {
     //2.遍历数组
            while(!stack.isEmpty() && prices[stack.peek()] >= prices[i]){
     //3.如果栈不为空并且栈顶元素对应的价格大于等于当前元素的价格
                prices[stack.pop()] -= prices[i]; //3.1 栈顶元素出栈并更新其价格
            }
            stack.push(i); //4.将当前元素下标加入栈中
        }
        return prices; //5.返回更新后的prices数组
    }
}

class Solution {
    public int[] finalPrices(int[] prices) {
        int secondPointer; // 定义第二个指针
        for (int i = 0; i < prices.length - 1; i++) {
     // 遍历prices数组
            secondPointer = i + 1; // 第二个指针从i+1开始
            while (secondPointer < prices.length && prices[i] < prices[secondPointer]) {
     // 如果第二个指针在数组长度范围内，并且第二个指针所指的数值大于第一个指针所指的数值
                secondPointer++; // 将第二个指针向后移动
            }
            if (secondPointer < prices.length && secondPointer > i && prices[i] >= prices[secondPointer]) {
     // 如果第二个指针在数组长度范围内，并且第二个指针的下标大于第一个指针的下标，同时第一个指针所指的数值大于等于第二个指针所指的数值
                prices[i] -= prices[secondPointer]; // 将第二个指针所指的数值从第一个指针所指的数值中减去
            }
        }
        return prices; // 返回处理后的数组
    }
}
class Solution {
    public int[] finalPrices(int[] prices) {
        Stack<Integer> st=new Stack<>(); //1.定义一个栈
        for(int i=prices.length-1;i>=0;i--){
     //2.从后往前遍历价格数组
            while(st.size()>0&&st.peek()>prices[i]) //3.当栈不为空且栈顶元素大于当前元素时，弹出栈顶元素
            st.pop();
            int n=prices[i];
            if(!st.isEmpty()) //4.如果栈不为空，说明有元素可以进行折扣
            prices[i]=prices[i]- st.peek(); //5.将当前元素减去栈顶元素，得到最终价格
            st.push(n); //6.将当前元素压入栈中
        }
        return prices; //7.返回最终价格数组
    }
}

注释：从后向前遍历数组的原因
从后向前遍历数组是为了能够利用·单调栈的特性。
单调栈是一种栈的应用，用于维护一个单调递增或单调递减的栈。在这道题中，我们需要找到当前元素后面第一个小于等于它的数，如果从后向前遍历数组，则可以用单调递减栈来维护后面的元素。
具体来说，在遍历到当前元素时，如果栈顶元素大于当前元素，则可以弹出栈顶元素并更新它的值，直到栈为空或栈顶元素小于等于当前元素。
这样，当我们找到当前元素后面第一个小于等于它的数时，我们已经将栈中所有比它大的元素弹出了，栈顶元素即为所求的元素。
由于我们从后向前遍历数组，所以栈中的元素是按照从后往前的顺序入栈的，满足单调递减的性质。

class Solution {
     public  int[] finalPrices(int[] prices) {
        int[] res = new int[n];//1.定义res数组和Stack
        Stack<Integer> stack = new Stack<>();
        for (int i = prices.length - 1; i >= 0; i--) {
    //2.for循环遍历，倒序遍历插入stack
            while (!stack .isEmpty() && prices[i] < stack .peek()) stack.pop();//当stack不为空并且prices的i值小于弹出的元素，删除stack的头部元素
            res[i] = prices[i] - (stack .isEmpty() ? 0 : stack .peek());//如果stack不为空，prices[i] -st.peek()，否则为prices[i]
            stack .push(prices[i]);//stack中添加元素
        }
        return res;
    }
}