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

题目大意：

商品折扣后的最终价格

给你一个数组 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 <= 500
• 1 <= prices[i] <= 10^3

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1475

解题思路分析：

解法一：暴力算法

本题数据规模不大，因此暴力算法完全可行。使用二层循环，第一层循环遍历每个数字，第二层循环从当前数字后一位开始向后循环，找到第一个小于等于当前数字后，退出第二层循环，两个数字差为当前结果。如果第二层循环中未找到合理答案时，当前数字即是当前结果。本解法时间复杂度为O(n^2)。

实现代码：

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

本题解法执行时间为2ms。

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]

如果使用暴力解，每次都要遍历到最后一位，才能找到第一个小于自身的数字，这样一来，如果数组长度是百万级别以上的话，n平方的时间复杂度大概率会TLE超时。

因此我们不妨将数据做下预处理，如果我们能够事先知道每个数字之后距离最近的小于等于自身数字的下标，那么就会方便许多，例如上例，我们可以推导出：

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

即每个数字之后第一个小于等于自身的数字都是下标为8的那个元素。这样一来，我们使用一层循环就可以得出答案，如果当前数字所在下标与距离自身最近的小于等于自身的下标相同时，代表没有折扣，直接返回当前数字，反之，用当前数字减去最小下标代表的数字后即是答案。

最后来看如何推导出min数组。我们从数组最后一位向前循环，当前下标为i。最后一位数字肯定不会有折扣，因此最后一位的min值为自身，即min[i]=i。除此之外，如果当前数字大于等于后一位数字，那么当前数字的min值为后一位的下标，即min[i]=i+1。反之，如果后一位数字大于当前数字，我们继续查看后一位数字的第一个小于它的数字，如果该数字小于等于当前数字，该数字的下标即是当前的min值，反之继续查看该数字的后面第一个小于它的数字，重复此循环，直到找到为止。如果最终也没找到，那么说明当前数字之后再无比自身小的数字，那么当前数字的min值为当前index，即min[i]=i。这个思路实际上有些类似于记忆数组或者是动态规划。

实现代码：

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

本题解法执行时间为1ms。

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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1475-final-prices-with-a-special-discount-in-a-shop-解题思路分析/