搜索
首页后端开发php教程商店特别折扣的最终价格

Final Prices With a Special Discount in a Shop

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

难度:简单

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

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

店内商品有特别折扣。如果您购买第 ith 件商品,那么您将获得相当于价格[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中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
继续使用PHP:耐力的原因继续使用PHP:耐力的原因Apr 19, 2025 am 12:23 AM

PHP仍然流行的原因是其易用性、灵活性和强大的生态系统。1)易用性和简单语法使其成为初学者的首选。2)与web开发紧密结合,处理HTTP请求和数据库交互出色。3)庞大的生态系统提供了丰富的工具和库。4)活跃的社区和开源性质使其适应新需求和技术趋势。

PHP和Python:探索他们的相似性和差异PHP和Python:探索他们的相似性和差异Apr 19, 2025 am 12:21 AM

PHP和Python都是高层次的编程语言,广泛应用于Web开发、数据处理和自动化任务。1.PHP常用于构建动态网站和内容管理系统,而Python常用于构建Web框架和数据科学。2.PHP使用echo输出内容,Python使用print。3.两者都支持面向对象编程,但语法和关键字不同。4.PHP支持弱类型转换,Python则更严格。5.PHP性能优化包括使用OPcache和异步编程,Python则使用cProfile和异步编程。

PHP和Python:解释了不同的范例PHP和Python:解释了不同的范例Apr 18, 2025 am 12:26 AM

PHP主要是过程式编程,但也支持面向对象编程(OOP);Python支持多种范式,包括OOP、函数式和过程式编程。PHP适合web开发,Python适用于多种应用,如数据分析和机器学习。

PHP和Python:深入了解他们的历史PHP和Python:深入了解他们的历史Apr 18, 2025 am 12:25 AM

PHP起源于1994年,由RasmusLerdorf开发,最初用于跟踪网站访问者,逐渐演变为服务器端脚本语言,广泛应用于网页开发。Python由GuidovanRossum于1980年代末开发,1991年首次发布,强调代码可读性和简洁性,适用于科学计算、数据分析等领域。

在PHP和Python之间进行选择:指南在PHP和Python之间进行选择:指南Apr 18, 2025 am 12:24 AM

PHP适合网页开发和快速原型开发,Python适用于数据科学和机器学习。1.PHP用于动态网页开发,语法简单,适合快速开发。2.Python语法简洁,适用于多领域,库生态系统强大。

PHP和框架:现代化语言PHP和框架:现代化语言Apr 18, 2025 am 12:14 AM

PHP在现代化进程中仍然重要,因为它支持大量网站和应用,并通过框架适应开发需求。1.PHP7提升了性能并引入了新功能。2.现代框架如Laravel、Symfony和CodeIgniter简化开发,提高代码质量。3.性能优化和最佳实践进一步提升应用效率。

PHP的影响:网络开发及以后PHP的影响:网络开发及以后Apr 18, 2025 am 12:10 AM

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

PHP类型提示如何起作用,包括标量类型,返回类型,联合类型和无效类型?PHP类型提示如何起作用,包括标量类型,返回类型,联合类型和无效类型?Apr 17, 2025 am 12:25 AM

PHP类型提示提升代码质量和可读性。1)标量类型提示:自PHP7.0起,允许在函数参数中指定基本数据类型,如int、float等。2)返回类型提示:确保函数返回值类型的一致性。3)联合类型提示:自PHP8.0起,允许在函数参数或返回值中指定多个类型。4)可空类型提示:允许包含null值,处理可能返回空值的函数。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

功能强大的PHP集成开发环境

SecLists

SecLists

SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)