stellogic的个人空间
贪心
stellogic Two
  2025-11-09 07:05:31   2025-11-09 07:05:31    

121. 买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-100-liked
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104

对于每一天，如果我们选择在今天卖出，那么我们应该在今天之前的最低价格买入。

我们考虑固定卖出的日子，是因为这样我们需要的是之前遍历过的最低的，我们只需要回顾历史信息不需要预测还未遍历的信息。反之如果固定买入的日子，需要预测还未遍历过的信息。

这样就把问题转化为一个可以在迭代中、仅利用历史信息就能做出最优决策的形式。

遍历同时维护最小值，时刻更新差即可。最终差和0比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Map;

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int minPriceBefore = prices[0];
        int maxIncome = Integer.MIN_VALUE;
        for (int i = 1; i < prices.length; i++) {
            maxIncome = Math.max(maxIncome,prices[i] - minPriceBefore);
            minPriceBefore = Math.min(minPriceBefore,prices[i]);
        }
        return Math.max(0,maxIncome);
    }
}

时间O(n),空间O(1)

55. 跳跃游戏

https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-100-liked

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 104
0 <= nums[i] <= 105

感觉是个动态规划

状态定义为i，当前位于的坐标

dp[i]表示能否到达索引为i

dp[i] = 求或集(dp[k] && k + nums[k] >= i) ，i从0到i-1

复杂度，0+1+2+……n-1是O(n^2)

空间复杂度O(n)

DP思路是：dp[i] = OR(dp[k] && k + nums[k] >= i) for 0 <= k < i。

我们来观察这个式子：为了让 dp[i] 为 true，我们只需要存在任何一个 k 满足条件即可。

我们不必每次都回头检查所有的 k。我们可以一边遍历，一边维护一个变量 maxReach，这个变量记录了 max(k + nums[k])，其中 k 是所有已经确认为可达（dp[k]为true）的位置。

那么，判断 dp[i] 是否为 true，就等价于判断 i 是否小于等于 i-1 计算出的 maxReach。

事实上贪心算法

  1. 贪心

维护一个maxReach，表示当前可以抵达的最远距离

遍历数组

对于每个位置，先判断是否可以抵达，不可以直接返回false；更新maxReach，如果maxReach大于最远坐标直接返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length <= 1){
            return true;
        }
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (maxReach < i){
                return false;
            }
            maxReach = Math.max(maxReach,i + nums[i]);
            if (maxReach >= nums.length-1){
                return true;
            }
        }
        return true;
    }
}

时间O(n),空间O(n)

45. 跳跃游戏 II

https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-liked

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 n - 1

维护三个变量

jumps: 当前的跳跃次数。

current_end: 当前这一跳所能到达的最远边界。

farthest: 跳跃能到达的最远位置

假设我们已经用了 k 步，能到达的最远距离是 current_end。现在我们需要迈出第 k+1 步。

我们的出发点可以是上一步能到达的任何位置（即从上一个边界到 current_end 之间的所有位置）。

在所有这些可能的出发点中，我们选择那个能让第 k+1 步跳完后，总覆盖范围最远的那个。

这个“最远的覆盖范围”就是 farthest 变量所记录的。

递推可以得到每次我们都能得到第j次跳跃所能达到的最远距离

直到这个边界大于等于终点

具体流程

  1. 初始化 jumps = 0, current_end = 0, farthest = 0。
  2. 我们从左到右遍历数组（从 i = 0 到 n-2，因为到达倒数第二个位置时，总能跳到最后一个位置，无需再更新）。
  3. 在遍历每个位置 i 时，我们更新 farthest 的值，farthest = max(farthest, i + nums[i])。这代表了从第 jumps 次跳跃的覆盖范围内（即 0 到 current_end），再跳一次能到达的最远距离。
  4. 当 i 到达了 current_end 时，意味着我们已经走完了上一次跳跃能覆盖的所有范围。此时，我们必须进行下一次跳跃。
    • 我们将 jumps 加 1。
    • 我们将 current_end 更新为新的 farthest，这为下一次跳跃设定了新的边界。
  5. 遍历结束后，jumps 就是到达终点的最小跳跃次数。

我们希望前n-1次跳的尽可能远

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int jump(int[] nums) {
        int jumps = 0;
        int current_end = 0;
        int farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest,i+nums[i]);
            if (i == current_end){
                jumps++;
                current_end = farthest;
            }
        }
        return jumps;
    }
}

时间O(N)空间O(1)

  1. 图

事实上可以把这个数组每个元素看成一个节点，i如果能到j就代表i到j有一条边

那么这个问题就是从0节点到n-1节点的最近距离

使用BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }

        // 队列存储的是数组的下标
        Queue<Integer> queue = new LinkedList<>();
        // visited数组用于标记某个位置是否已经访问过，防止重复入队
        boolean[] visited = new boolean[nums.length];

        // 1. 初始化
        queue.offer(0); // 从下标0开始
        visited[0] = true;
        int jumps = 0; // 跳跃次数

        // 2. 开始BFS分层遍历
        while (!queue.isEmpty()) {
            // 获取当前层有多少个节点需要处理
            int levelSize = queue.size();
            jumps++; // 进入新的一层，跳跃次数加1

            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                int currentPos = queue.poll();

                // 从当前位置，计算所有可以到达的下一个位置
                int maxJump = nums[currentPos];
                for (int j = 1; j <= maxJump; j++) {
                    int nextPos = currentPos + j;

                    // 如果下一个位置就是终点，我们已经找到了最短路径
                    if (nextPos >= nums.length - 1) {
                        return jumps;
                    }

                    // 如果下一个位置没有被访问过，则加入队列并标记
                    if (!visited[nextPos]) {
                        visited[nextPos] = true;
                        queue.offer(nextPos);
                    }
                }
            }
        }

        return jumps; // 理论上因为题目保证能到达，不会执行到这里
    }
}

时间O(N+V),V最坏的情况，比如每个元素都是n，是N^2,因此是O(N^2)

空间O(N)

上面可以进一步优化

有很多重复的工作。

我们可以给每层遍历到的最远的索引记为farthest

farthest之前的节点必定都被遍历过了，下次遍历直接从farthest开始即可

优化后也就实际上就是贪心算法

广度优先搜索 (BFS) 概念 贪心算法实现 解释
层的层数 (Level Number) 变量 jumps BFS 每扩展一层，jumps 就加一，代表需要多跳一次。
当前层的边界 变量 current_end 在BFS中，处理完一层才能进入下一层。current_end 标记了当前这一跳（这一层）所能覆盖的最远索引。当遍历指针 i 到达 current_end 时，就意味着当前层已经遍历完毕。
下一层的所有节点 变量 farthest 在通用BFS中，我们需要一个队列来存储下一层的所有节点。但在这里，因为节点的“连续性”，我们不需要存储所有节点，只需要知道下一层所能到达的最远边界即可。这个边界就是 farthest。
遍历当前层的所有节点 for 循环中的指针 i for 循环从上一层的边界之后开始，一直遍历到 current_end，这个过程就等价于遍历BFS当前层的所有节点，并为计算下一层的边界做准备。

763. 划分字母区间

https://leetcode.cn/problems/partition-labels/description/?envType=study-plan-v2&envId=top-100-liked

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、”defegde”、”hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。
示例 2：

输入：s = “eccbbbbdec”
输出：[10]

提示：

1 <= s.length <= 500
s 仅由小写英文字母组成

先遍历一次 ，耗费O(n)，使用一个哈希表统计每个字母的出现过的索引。

然后再次开始遍历字符串，指针记为cur。

每个字符读取后，获取它对应的出现索引，当前索引和对应的最大的索引作为可能被分割的一个小字符串。起点记为startTemp,最大索引记为endTemp。

之后cur移动，读取startTemp和endTemp之间的每个字符，获取对应的索引，判断最大索引是否超过endTemp。

如果超过，endTemp更新为这个最大索引。循环，直到cur指向endTemp。把这个加入结果。

最终时间复杂度O(n),空间O(n)

不过事实上我们只关心字母出现的组后索引，不必记录所有索引。使用数组记录，空间O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        int[] last_index = new int[26];
        int startTemp = Integer.MAX_VALUE;
        int endTemp = Integer.MIN_VALUE;
        //startTemp = Integer.MAX_VALUE;:
        //目的: 确保在循环的第一次迭代时 (cur = 0)，条件 cur > startTemp (即 0 > 2147483647) 绝对为假。
        //效果: 这就强制程序在开始时必须进入 else 块，从而正确地初始化第一个分区的 startTemp 和 endTemp。
        //endTemp = Integer.MIN_VALUE;:
        //目的: 这是一个标准的初始化方法，当需要在一系列数字中找最大值时使用。
        //效果: 任何一个有效的索引 i 都比 Integer.MIN_VALUE 大，所以第一次调用 Math.max(..., endTemp) 时，总能正确地将 endTemp 设置为第一个遇到的真实边界。
        //重置: 当你找到一个划分并将其加入 result 后，将它们重置为 MAX_VALUE 和 MIN_VALUE。这同样是为了让下一次循环迭代时，cur > startTemp 再次为假，从而触发 else 逻辑来开启一个新的划分。

        for (int i = 0; i < s.length(); i++) {
            last_index[s.charAt(i)-'a'] = i;
        }
        for (int cur = 0; cur < s.length(); cur++) {
            if (cur > startTemp){
                char theChar = s.charAt(cur);
                endTemp = Math.max(last_index[theChar - 'a'],endTemp) ;
                if (endTemp >= s.length()-1){
                    result.add(endTemp-startTemp+1);
                    break;
                }
            }else {
                startTemp = cur;
                char theChar = s.charAt(cur);
                endTemp = last_index[theChar-'a'];
            }
            if (cur == endTemp){
                result.add(endTemp - startTemp+1);
                endTemp = Integer.MIN_VALUE;
                startTemp = Integer.MAX_VALUE;
                continue;
            }

        }
        return result;
    }
}

下面是更好的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        // 1. 预处理，记录每个字母最后出现的位置 (这部分和你的一样)
        int[] lastIndices = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastIndices[s.charAt(i) - 'a'] = i;
        }

        // 2. 第二次遍历，进行划分
        int start = 0; // 当前分区的起始位置
        int end = 0;   // 当前分区需要到达的最远边界

        for (int i = 0; i < s.length(); i++) {
            // 对于当前字符，更新我们的最远边界
            // Math.max确保了end总是当前扫描过的所有字符的最远边界
            end = Math.max(end, lastIndices[s.charAt(i) - 'a']);


            // 如果当前位置i已经到达了最远边界end
            // 这意味着[start, end]区间内的所有字符都已“闭合”
            // 它们的最远出现位置都不会超过end
            if (i == end) {
                // 找到了一个划分，计算其长度并添加到结果中
                result.add(end - start + 1);
                // 更新下一个分区的起始位置
                start = i + 1;
            }
        }
        return result;
    }
}

贪心体现在：

要想让片段的总数量最多，那么我们应该让每一个片段的长度尽可能短。

如果你在某个位置可以做出一个合法的划分，那么你就应该立刻划分，而不是继续向后延伸，因为延伸会让当前划分变长，从而可能减少后续的划分机会，导致总划分数变少。

贪心
2025/11/09/贪心/
作者
stellogic
发布于
2025-11-09 07:05
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 1. 121. 买卖股票的最佳时机
  2. 2. 55. 跳跃游戏
  3. 3. 45. 跳跃游戏 II
  4. 4. 763. 划分字母区间
  1. 1. 121. 买卖股票的最佳时机
  2. 2. 55. 跳跃游戏
  3. 3. 45. 跳跃游戏 II
  4. 4. 763. 划分字母区间