商店特别折扣的最终价格

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]

约束：

• 1
• 1

提示：

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

解决方案：

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

方法：

1. 堆栈方法:

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

2. 边缘情况：如果数组中后面没有任何商品的价格更小，则不应用折扣。

让我们用 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]
?>

解释：

1. 初始化:

   • 创建一个与$prices大小相同的数组$result，并将其初始化为0。

2. 外循环:

   • 循环遍历索引 $i 处的每个价格，计算折扣后的最终价格。

3. 内循环:

   • 对于每个价格 $i，迭代后续价格 $j（其中 $j > $i）。
   • 检查$prices[$j]是否小于或等于$prices[$i]。如果为 true，则设置 $discount = $prices[$j] 并退出内循环。

4. 最终价格计算：

   • 从 $prices[$i] 中减去找到的折扣并将结果存储在 $result[$i] 中。

5. 返回结果:

   • 处理完所有价格后，返回最终结果数组。

复杂：

• 时间复杂度：O(n²)（由于每个价格的嵌套循环）。
• 空间复杂度：O(n)（对于结果数组）。

示例输出：

• 对于价格 = [8, 4, 6, 2, 3]，输出为 [4, 2, 4, 2, 3]。
• 对于价格 = [1, 2, 3, 4, 5]，输出为 [1, 2, 3, 4, 5]。
• 对于价格 = [10, 1, 1, 6]，输出为 [9, 0, 1, 6]。

即使它不是最优化的解决方案，这种方法也能在问题的限制范围内发挥作用 (1

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是商店特别折扣的最终价格的详细内容。更多信息请关注PHP中文网其他相关文章！