力扣1475. 商品折扣后的最终价格python实现

1475. 商品折扣后的最终价格python实现

一、问题描述

二、算法思想

  从当前列表元素的后一个位置开始向后查找，找到比当前位置的元素小的元素后就对当前元素进行处理，找不到则不处理，时间复杂度O(n^2)。

三、代码

class Solution(object):def finalPrices(self, prices):""":type prices: List[int]:rtype: List[int]"""length = len(prices)b = 0 #表示x的下标for b in range(length):# 用x in prices会因为prices的元素改变而无法准确找到x的下标  for c in range(b+1,length):if prices[b] >= prices[c]:prices[b] -= prices[c] breakreturn prices

四、题目链接

https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/