LeetCode（Stack)1475. Final Prices With a Special Discount in a Shop

短命女 2023-09-25 21:36 76阅读 0赞

# 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;
        }
    }