📚 plmblog

Appearance

13-贪心

📅 发表于 2026/06/07
🔄 更新于 2026/06/07
👁️ -- 次访问
📝 0 字
⏳ 0 分钟

题目 ​

01-121-买卖股票的最佳时机 ​

01-121-买卖股票的最佳时机

leetcode-121

  • 输入：prices，代表一只股票每天的价格。可以购买卖出。只能买1次、卖1次。
  • 输出：最大收益。
  • [7,1,5,3,6,4] --> 5
    • 在第2天买入price=1，第5天卖出price=6，收益=6-1=5

最低价格最高利润贪心法 ​

最低价格最高利润贪心法

两个关键变量

  • 历史最低价：一直遍历更新。
  • 今日卖出最大利润：今日价格-历史最低价
  • 最大利润：每日最大利润最大值

贪心

  • 买入贪心：历史最低价 买入。min_price
  • 卖出贪心：最高点 卖出。max_profit

遍历计算

  • 遍历每个价格，依次计算：
    • 历史最低价格买，今日卖的利润
    • 更新最大利润
    • 更新历史最低价格
python
def maxProfit(self, prices: List[int]) -> int:
    if not prices or len(prices) == 1:
        return 0

    # 历史最低价格
    min_price = prices[0]
    # 最大利润
    max_profit = 0

    # 依次计算，按照历史最低价格买入，每天卖出获得的利润
    for price in prices[1:]:
        # 历史最低价格买，今日卖的利润
        profit = price - min_price
        # 更新最大利润
        max_profit = max(max_profit, profit)  

        # 更新历史最低价格
        min_price = min(price, min_price)  

    return max_profit

01-122-买卖股票的最佳时机2 ​

01-122-买卖股票的最佳时机2

leetcode-122

  • 输入：某只股票每日价格 prices 数组。
  • 股票买卖：在任何时候，最多只能持有 1股股票，可以多次买卖股票。
  • 输出：最大利润

示例

  • [7,1,5,3,6,4]
    • 第2天买，第3天卖：利润=5-1=4
    • 第4天买，第5天卖：利润=6-3=3
    • 总利润：4+3=7
  • [1,2,3,4,5]
    • 第1天买，第5天卖，利润=5-1=4
    • 总利润：4
  • [7,6,4,3,1]
    • 无法获得利润，总利润0

贪心多次买卖股票 ​

贪心多次买卖股票

牛市股票长线利润==每日增长之和

  • 牛市股票长线利润 总涨幅 == 每日微小涨幅之和
  • 每日价格：[3, 5, 8]
    • 策略1：第1天买，第3天卖。总利润：8-3=5
    • 策略2：第1天买，第2天卖，利润 5-3=2；第2天买，第3天卖，利润8-5=3。总利润：2+3=5

贪心策略

  • 假设昨天买入，今天卖出。
  • 只需关注 today 和yesterday
    • today > yesterday：涨了，卖掉；把微小涨幅拿到手。
    • today < yesterday：跌了，不管。
  • 求和 所有微小涨幅，即总利润。
python
def maxProfit(self, prices: List[int]) -> int:
    """可多次买卖股票，求总利润，贪心算法，只需拿到每日微小总涨幅，求和即可"""
    if not prices or len(prices) <= 1:
        return 0

    # 策略：昨天买，今天卖。
    # 累计利润求和
    sum_profit = 0

    for i in range(1, len(prices)):
        # 昨日价格
        yesterday_price = prices[i-1]
        # 今日价格
        today_price = prices[i]

        # 今日 > 昨日，则卖出，累计今日利润
        if today_price > yesterday_price:
            # 今日利润
            today_profit = today_price - yesterday_price
            # 每日利润累加
            sum_profit += today_profit
    return sum_profit

02-55-跳跃游戏 ​

02-55-跳跃游戏

leetcode-55

  • 输入：非负整数数组 nums，数组元素表示当前位置 能跳跃的最大步数，最初位于位置0。
  • 输出：能否到达最后一个位置。True False
  • [2,3,1,1,4] -> True。可先1步，再3步，到达最后位置。
  • [3,2,1,0,4] -> False。无论如何都会到达idx=3，但跳跃长度是0，无法跳跃。

贪心到达最远位置 ​

贪心到达最远位置
  • max_reach：最多能到达 哪个位置
  • 遍历每个位置i
    • 如果 i > max_reach：不可到达，返回False
    • 贪心更新 max_reach：max (max_reach, i+nums[i])
    • 如果：max_reach >= len(nums)-1，返回True
  • 返回False
python
def canJump(self, nums: List[int]) -> bool:
    """贪心法，解决可到达的最大位置"""
    if not nums:
        return False

    # 可到达的最大位置
    max_reach = 0 
    # 目标位置
    target_pos = len(nums) - 1

    for i, step in enumerate(nums):
        if max_reach < i: 
            # 过去 max_reach 已无法到达当前i
            return False
        # 能到达当前i，当前i能到达的最大位置
        cur_max_reach = i + step
        # 贪心更新 可到达最大位置
        max_reach = max(max_reach, cur_max_reach) 

        # 已能到达末尾位置
        if max_reach >= target_pos: 
            return True
    return False

03-45-跳跃游戏II ​

03-45-跳跃游戏II

leetcode-45

  • 输入：nums，nums[i] 表示在位置i，能跳跃的最大步数。
  • 输出：到达位置n-1的最小步数。保证可到达。

贪心到达最大位置记录步数 ​

重要

贪心

  • 看潜力更新极限边界，走到边界就做结算。

三元素

  • max_reach：下一步起跳潜力，下一步能到达的最远地方。
    • max_reach = max(max_reach, i+nums[i])
  • end：当前极限边界。到达这里就需重新起跳。
    • cur_step_end = max_reach，即 i+nums[i] 或 旧max_reach
  • steps：累计起跳步数。
python
def jump(self, nums: List[int]) -> int:
    """跳跃到n-1，需要的最少步数，保证可到达，贪心算法"""

    if not nums or len(nums) <= 1:
        return 0 

    # 核心1：下一步起跳【最远能接力到哪里】。一路上谁的潜力大就听谁的。
    max_reach = 0     
    # 核心2：当前这一步的【能量极限边界】。到了这里就必须强行触发起跳。
    cur_step_end = 0 
    # 核心3：【总共跳了多少步】。
    steps = 0
		
    # 只需遍历到倒数第二个位置即可，否则到了末尾还会计算1次跳跃
    for i in range(len(nums)-1): 
        # 贪心更新下一步起跳的最大位置
        max_reach = max(max_reach, i+nums[i])

        # 当前位置已到达当前步的最远位置，需要迈新的步子了
        if i == cur_step_end:  
            cur_step_end = max_reach 
            steps += 1

    return steps

04-763-划分字母区间 ​

04-763-划分字母区间

leetcode-763

  • 输入：字符串s
  • 目标：把s尽可能划分为多的片段。同一字母仅能在一个片段中。
  • 输出：所有子串的长度列表
  • 示例
    • ababcbaca defegde hijhklij --> [9, 7, 8]。
    • eccbbbbdec --> [10]

贪心分割边界子串 ​

贪心分割边界子串

三要素

  • last_pos：记录每个ch的最后出现位置。
  • start：每个子串/片段的开始位置。
  • end：每个子串/片段的结束位置。

遍历每个位置i-字符ch，寻找子串/片段

  • 贪心向右：必须保证当前ch的最后出现位置 在当前片段里
    • end = max(end, last_pos[i])
  • 若 i == end：
    • 说明[start,i]之间的所有ch 都在当前片段，未来 都不会出现
    • 找到片段：len = end-start+1
    • 更新 下一片段start：start = end + 1
python
def partitionLabels(self, s: str) -> List[int]:
    """贪心分割子串，last_pos, start, end"""
    if not s:
        return []

    # 记录每个ch的最后出现位置
    ch2last = {} 
    for idx, ch in enumerate(s):
        ch2last[ch] = idx

    res = []
    # 当前片段的起始值
    start, end = 0, 0

    # 依次遍历所有ch，查找所有可能片段
    for i, ch in enumerate(s):
        # 当前ch的最后出现位置
        last_pos = ch2last[ch]
        # 当前片段end 应该>=last_pos
        end = max(end, last_pos)  

        if i == end:  
            # 说明[start, end]之间所有字符，当前片段都已包含，未来不会出现
            cur_len = end - start + 1
            res.append(cur_len)
            # 下一片段起始值
            start = end + 1
    return res
总访客数：   ·   总访问量：
PLM's Blog @ 2016 - 2026