Python版_Leetcode_hot100系列(14)--贪心算法

class Solution:    def maxProfit(self, prices: List[int]) -> int:        """        一次遍历解法 - 时间复杂度O(n)，空间复杂度O(1)        """        min_price = float('inf')  # 当前最小价格        max_profit = 0            # 最大利润        for price in prices:            # 更新最小价格            if price < min_price:                min_price = price            # 计算当前利润            current_profit = price - min_price            # 更新最大利润            if current_profit > max_profit:                max_profit = current_profit        return max_profit

prices = [7, 1, 5, 3, 6, 4]初始：min_price = inf, max_profit = 0第1天：price = 7  min_price = min(inf, 7) = 7  current_profit = 7 - 7 = 0  max_profit = max(0, 0) = 0第2天：price = 1  min_price = min(7, 1) = 1  current_profit = 1 - 1 = 0  max_profit = max(0, 0) = 0第3天：price = 5  min_price = min(1, 5) = 1  current_profit = 5 - 1 = 4  max_profit = max(0, 4) = 4第4天：price = 3  min_price = min(1, 3) = 1  current_profit = 3 - 1 = 2  max_profit = max(4, 2) = 4第5天：price = 6  min_price = min(1, 6) = 1  current_profit = 6 - 1 = 5  max_profit = max(4, 5) = 5第6天：price = 4  min_price = min(1, 4) = 1  current_profit = 4 - 1 = 3  max_profit = max(5, 3) = 5结束：return max_profit = 5 ✅

class Solution:    def canJump(self, nums: List[int]) -> bool:        """        贪心解法（反向） - 时间复杂度O(n)，空间复杂度O(1)        """        if not nums:            return False        # 从终点开始，维护一个可到达的位置        reachable = len(nums) - 1        # 从倒数第二个位置开始向前遍历        for i in range(len(nums) - 2, -1, -1):            # 如果当前位置能跳到可到达位置            if i + nums[i] >= reachable:                reachable = i        # 检查起点是否可到达终点        return reachable == 0

示例1：nums = [2, 3, 1, 1, 4]初始：reachable = 4 (终点)第1步：i = 3, nums[3] = 1  检查：3 + 1 = 4 >= reachable = 4 ✓  更新：reachable = 3第2步：i = 2, nums[2] = 1  检查：2 + 1 = 3 >= reachable = 3 ✓  更新：reachable = 2第3步：i = 1, nums[1] = 3  检查：1 + 3 = 4 >= reachable = 2 ✓  更新：reachable = 1第4步：i = 0, nums[0] = 2  检查：0 + 2 = 2 >= reachable = 1 ✓  更新：reachable = 0  结束：reachable = 0 == 0 ✓ return True ✅示例2：nums = [3, 2, 1, 0, 4]初始：reachable = 4 (终点)第1步：i = 3, nums[3] = 0  检查：3 + 0 = 3 < reachable = 4 ✗  不更新：reachable = 4第2步：i = 2, nums[2] = 1  检查：2 + 1 = 3 < reachable = 4 ✗  不更新：reachable = 4第3步：i = 1, nums[1] = 2  检查：1 + 2 = 3 < reachable = 4 ✗  不更新：reachable = 4第4步：i = 0, nums[0] = 3  检查：0 + 3 = 3 < reachable = 4 ✗  不更新：reachable = 4结束：reachable = 4 != 0 ✗ return False ✅

class Solution:    def jump(self, nums: List[int]) -> int:        """        贪心解法（分层遍历） - 时间复杂度O(n)，空间复杂度O(1)        """        if len(nums) <= 1:            return 0        jumps = 0           # 跳跃次数        current_end = 0     # 当前层的最远位置        farthest = 0        # 下一层的最远位置        # 注意：不需要遍历最后一个元素        for i in range(len(nums) - 1):            # 更新下一层的最远位置            farthest = max(farthest, i + nums[i])            # 到达当前层边界，需要跳跃            if i == current_end:                jumps += 1                current_end = farthest                # 如果已经能到达终点，提前结束                if current_end >= len(nums) - 1:                    break        return jumps

示例1：nums = [2, 3, 1, 1, 4]初始：jumps = 0, current_end = 0, farthest = 0第1步：i = 0, nums[0] = 2  farthest = max(0, 0 + 2) = 2  i == current_end (0 == 0) ✓  jumps = 1, current_end = 2第2步：i = 1, nums[1] = 3  farthest = max(2, 1 + 3) = 4  i != current_end (1 != 2) ✗第3步：i = 2, nums[2] = 1  farthest = max(4, 2 + 1) = 4  i == current_end (2 == 2) ✓  jumps = 2, current_end = 4  current_end >= len(nums) - 1 (4 >= 4) ✓ break结束：return jumps = 2 ✅示例2：nums = [2, 3, 0, 1, 4]初始：jumps = 0, current_end = 0, farthest = 0第1步：i = 0, nums[0] = 2  farthest = max(0, 0 + 2) = 2  i == current_end (0 == 0) ✓  jumps = 1, current_end = 2第2步：i = 1, nums[1] = 3  farthest = max(2, 1 + 3) = 4  i != current_end (1 != 2) ✗第3步：i = 2, nums[2] = 0  farthest = max(4, 2 + 0) = 4  i == current_end (2 == 2) ✓  jumps = 2, current_end = 4  current_end >= len(nums) - 1 (4 >= 4) ✓ break结束：return jumps = 2 ✅

class Solution:    def partitionLabels(self, s: str) -> List[int]:        """        贪心解法 - 时间复杂度O(n)，空间复杂度O(1)        """        # 记录每个字母的最后出现位置        last_pos = {}        for i, char in enumerate(s):            last_pos[char] = i        result = []        start = 0      # 当前区间的开始位置        end = 0        # 当前区间的结束位置        for i, char in enumerate(s):            # 扩展当前区间的结束位置            end = max(end, last_pos[char])            # 到达当前区间结束位置            if i == end:                result.append(end - start + 1)                start = i + 1        return result

示例1：s = "ababcbacadefegdehijhklij"第1步：记录每个字母的最后位置  a: 8, b: 5, c: 7, d: 14, e: 15, f: 11, g: 13, h: 19, i: 22, j: 23, k: 20, l: 21第2步：遍历字符串，划分区间初始：start = 0, end = 0, result = []  i=0, char='a': end = max(0, 8) = 8  i=1, char='b': end = max(8, 5) = 8  i=2, char='a': end = max(8, 8) = 8  i=3, char='b': end = max(8, 5) = 8  i=4, char='c': end = max(8, 7) = 8  i=5, char='b': end = max(8, 5) = 8  i=6, char='a': end = max(8, 8) = 8  i=7, char='c': end = max(8, 7) = 8  i=8, char='a': end = max(8, 8) = 8  i == end (8 == 8) ✓  result.append(8 - 0 + 1) = [9]start = 9  i=9, char='d': end = max(9, 14) = 14  i=10, char='e': end = max(14, 15) = 15  i=11, char='f': end = max(15, 11) = 15  i=12, char='e': end = max(15, 15) = 15  i=13, char='g': end = max(15, 13) = 15  i=14, char='d': end = max(15, 14) = 15  i=15, char='e': end = max(15, 15) = 15  i == end (15 == 15) ✓  result.append(15 - 9 + 1) = [9, 7]start = 16  i=16, char='h': end = max(16, 19) = 19  i=17, char='i': end = max(19, 22) = 22  i=18, char='j': end = max(22, 23) = 23  i=19, char='h': end = max(23, 19) = 23  i=20, char='k': end = max(23, 20) = 23  i=21, char='l': end = max(23, 21) = 23  i=22, char='i': end = max(23, 22) = 23  i=23, char='j': end = max(23, 23) = 23  i == end (23 == 23) ✓  result.append(23 - 16 + 1) = [9, 7, 8]start = 24结束：return [9, 7, 8] ✅