商店特别折扣的最终价格-php教程-PHP中文网

商店特别折扣的最终价格

Mary-Kate Olsen

发布： 2024-12-24 09:45:39

原创

841 人浏览过

Final Prices With a Special Discount in a Shop

1475。最终价格在商店有特别折扣

难度：简单

主题：数组、堆栈、单调堆栈

给你一个整数数组prices，其中prices[i]是商店中第i^个个商品的价格。

店内商品有特别折扣。如果您购买第 i^th 件商品，那么您将获得相当于价格[j]的折扣，其中 j 是满足 j > 的最小索引。 i 且价格[j]

返回一个整数数组答案，其中answer[i]是您为商店第i^第件商品支付的最终价格，考虑到特别折扣。

示例1：

输入： 价格 = [8,4,6,2,3]
输出： [4,2,4,2,3]
说明：
- 对于价格[0]=8的商品0，您将获得相当于价格[1]=4的折扣，因此，您将支付的最终价格是8 - 4 = 4。
- 对于价格[1]=4的商品1，您将获得相当于价格[3]=2的折扣，因此，您将支付的最终价格为4 - 2 = 2。
- 对于价格[2]=6的商品2，您将获得相当于价格[3]=2的折扣，因此，您将支付的最终价格为6 - 2 = 4。
- 对于第 3 项和第 4 项，您将不会获得任何折扣。

示例2：

输入： 价格 = [1,2,3,4,5]
输出： [1,2,3,4,5]
说明：在这种情况下，对于所有商品，您将不会获得任何折扣。

示例 3：

输入： 价格 = [10,1,1,6]
输出： [9,0,1,6]

约束：

提示：

使用暴力破解：对于有循环的商店中的第 i 个商品，找到第一个满足条件的位置 j 并应用折扣，否则折扣为 0。

解决方案：

我们需要根据后续商品的价格小于或等于当前价格的情况来应用特殊折扣，我们可以使用暴力的方法。我们将迭代价格数组，并针对每个商品查找其后价格较低或相等的第一个商品。这可以通过嵌套循环来实现。我们可以利用堆栈来有效地跟踪商品的价格并应用特别折扣。

方法：

堆栈方法:
- 我们可以从左到右迭代价格数组。对于每件商品，我们将使用堆栈来跟踪尚未找到折扣的价格。
- 对于每个价格，我们都会检查它是否小于或等于堆栈顶部的价格。如果是这样，那就意味着我们可以申请折扣。
- 堆栈将存储商品的索引，对于每个商品，我们将检查当前价格是否大于堆栈中索引处的价格，这意味着没有折扣。否则，通过从当前价格中减去相应的价格来应用折扣。
边缘情况：如果数组中后面没有任何商品的价格更小，则不应用折扣。

让我们用 PHP 实现这个解决方案：1475。最终价格在商店有特别折扣

<?php
/**
 * @param Integer[] $prices
 * @return Integer[]
 */
function finalPrices($prices) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$prices1 = [8, 4, 6, 2, 3];
$prices2 = [1, 2, 3, 4, 5];
$prices3 = [10, 1, 1, 6];

print_r(finalPrices($prices1)); // Output: [4, 2, 4, 2, 3]
print_r(finalPrices($prices2)); // Output: [1, 2, 3, 4, 5]
print_r(finalPrices($prices3)); // Output: [9, 0, 1, 6]
?>

登录后复制

解释：

初始化:
- 创建一个与$prices大小相同的数组$result，并将其初始化为0。
外循环:
- 循环遍历索引 $i 处的每个价格，计算折扣后的最终价格。
内循环:
- 对于每个价格 $i，迭代后续价格 $j（其中 $j > $i）。
- 检查$prices[$j]是否小于或等于$prices[$i]。如果为 true，则设置 $discount = $prices[$j] 并退出内循环。
最终价格计算：
- 从 $prices[$i] 中减去找到的折扣并将结果存储在 $result[$i] 中。
返回结果:
- 处理完所有价格后，返回最终结果数组。