hot100贪心算法题解

发表于 2025/01/20 更新于 2025/01/20

作者 匆匆那年 28 分钟阅读

121. 买卖股票的最佳时机

问题描述

给定一个数组 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 <= p r i c e s . l e n g t h <= 10^{5}$
$0 <= p r i c e s [i] <= 10^{4}$

题解

这个问题的核心是求解如何从给定的股票价格数组中找出买入和卖出的时机，以获得最大利润。我们需要找到一个合适的买入时机和卖出时机，使得两者之间的差值最大。

思路

为了求解这个问题，我们可以通过一次遍历来计算最大利润：

最小值和最大利润：
- 假设我们在遍历过程中维护两个变量：
  - minPrice：记录到当前为止的最低股票价格。
  - maxProfit：记录能够获得的最大利润。
遍历过程：
- 对于每一天的价格 price，我们可以考虑：
  - 如果今天的价格比 minPrice 小，更新 minPrice 为今天的价格。
  - 否则，计算当前价格和 minPrice 之间的差值，更新 maxProfit 为当前利润与之前最大利润的较大值。
时间复杂度：
- 由于我们只需要遍历一次数组，时间复杂度是 O(n)，其中 n 是股票价格数组的长度。
空间复杂度：
- 我们只需要常数空间来存储 minPrice 和 maxProfit，因此空间复杂度是 O(1)。

代码实现

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;  // 初始化为最大整数，表示尚未找到价格
        int maxProfit = 0;  // 最大利润初始化为0
        
        // 遍历价格数组
        for (int price : prices) {
            // 更新最低价格
            minPrice = min(minPrice, price);
            
            // 计算当前利润
            maxProfit = max(maxProfit, price - minPrice);
        }
        
        return maxProfit;
    }
};

int main() {
    Solution solution;
    
    // 示例 1
    vector<int> prices1 = {7, 1, 5, 3, 6, 4};
    cout << solution.maxProfit(prices1) << endl;  // 输出: 5
    
    // 示例 2
    vector<int> prices2 = {7, 6, 4, 3, 1};
    cout << solution.maxProfit(prices2) << endl;  // 输出: 0
    
    return 0;
}

代码解释

minPrice：初始化为 INT_MAX，表示最初未找到任何价格。我们在遍历中不断更新它，确保它始终保持最小的价格。
maxProfit：初始化为 0，表示初始时没有利润。在遍历过程中，我们计算每一天的利润，并更新 maxProfit。
遍历价格数组：我们遍历数组中的每一天价格，更新 minPrice 和 maxProfit，从而获得最大利润。
返回最大利润：遍历结束后，maxProfit 就是我们能获得的最大利润。

示例解析

示例 1

输入：

[7, 1, 5, 3, 6, 4]

输出：

5

解释：

最低价格出现在第 2 天（价格 = 1）。
最高利润是在第 5 天卖出（价格 = 6），所以利润是 6 - 1 = 5。

示例 2

输入：

[7, 6, 4, 3, 1]

输出：

0

解释：

股票价格不断下降，没有利润可获取，因此最大利润为 0。

边界情况

只有一个价格：
- 如果数组长度为 1，则无法进行交易，利润为 0。
价格递减：
- 如果价格是递减的，则无法获利，最大利润为 0。
价格相等：
- 如果所有价格相等，买入和卖出的价格相同，利润为 0。

时间和空间复杂度

时间复杂度：O(n)，我们只需要遍历一次价格数组。
空间复杂度：O(1)，只用了常数空间。

总结

这个问题利用了贪心算法的思想，通过一次遍历就可以计算出最大利润。维护 minPrice 和 maxProfit 两个变量，可以高效地解决问题。

55. 跳跃游戏

问题描述

给你一个非负整数数组 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 <= n u m s . l e n g t h <= 10^{4}$
$0 <= n u m s [i] <= 10^{5}$

题解

这个问题的核心是判断从数组的第一个元素开始，是否能够跳跃到达数组的最后一个元素。每个数组元素代表当前下标可以跳跃的最大长度，我们需要判断是否可以通过一次或多次跳跃到达数组的最后。

思路

我们可以使用 贪心算法 来解决这个问题。我们遍历数组，保持一个变量 maxReach，表示当前能够到达的最远下标。对于每个位置 i，如果当前位置可达（即 i <= maxReach），我们就更新 maxReach 为 max(maxReach, i + nums[i])，即从当前位置跳跃后能到达的最远位置。如果在某个时刻 maxReach 大于等于最后一个下标，我们就返回 true，表示可以到达最后一个下标。如果遍历结束后仍然无法到达最后一个下标，返回 false。

具体步骤

初始化 maxReach 为 0。
遍历数组：
- 如果当前下标 i 超过了 maxReach，说明无法从当前位置跳跃到该位置，直接返回 false。
- 更新 maxReach 为 max(maxReach, i + nums[i])。
- 如果 maxReach 已经大于等于最后一个下标，返回 true。
如果遍历结束后 maxReach 小于数组的最后一个下标，返回 false。

代码实现

  
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;  // 记录当前能够到达的最远位置
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            if (i > maxReach) {
                // 如果当前位置无法到达，返回 false
                return false;
            }
            
            // 更新最远能够到达的位置
            maxReach = max(maxReach, i + nums[i]);
            
            // 如果已经能够到达最后一个位置，直接返回 true
            if (maxReach >= n - 1) {
                return true;
            }
        }
        
        return false;  // 如果遍历结束后还不能到达最后一个位置，返回 false
    }
};

int main() {
    Solution solution;
    
    // 示例 1
    vector<int> nums1 = {2, 3, 1, 1, 4};
    cout << boolalpha << solution.canJump(nums1) << endl;  // 输出: true
    
    // 示例 2
    vector<int> nums2 = {3, 2, 1, 0, 4};
    cout << boolalpha << solution.canJump(nums2) << endl;  // 输出: false
    
    return 0;
}

代码解释

变量 maxReach：
- maxReach 记录我们能够跳跃到的最远位置。初始时，它是 0，表示只能在数组的起始位置。
遍历数组：
- 如果 i > maxReach，意味着当前下标 i 无法到达，直接返回 false。
- 否则，我们更新 maxReach，确保它记录的是从当前位置跳跃后能到达的最远位置。
- 如果 maxReach 大于等于数组的最后一个下标，说明我们已经能够到达最后一个位置，直接返回 true。
结束遍历：
- 如果遍历完成后，maxReach 仍然小于数组的最后一个下标，说明无法到达最后，返回 false。

示例解析

示例 1

输入：

[2, 3, 1, 1, 4]

输出：

true

解释：

从第 0 个位置出发，跳跃最大 2 步，可以到达第 1 或第 2 个位置。
在第 1 个位置，可以跳跃 3 步，到达最后一个位置。因此可以到达最后一个下标。

示例 2

输入：

[3, 2, 1, 0, 4]

输出：

false

解释：

从第 0 个位置出发，最多可以跳跃 3 步，能够到达第 3 个位置。
在第 3 个位置，我们无法再向前跳跃（跳跃长度为 0），因此无法到达最后一个位置。

边界情况

数组长度为 1：
- 只有一个元素时，不需要跳跃，已经在最后一个位置，返回 true。
全部为 0 的数组：
- 如果数组中所有元素都是 0，且数组长度大于 1，无法跳跃到其他位置，返回 false。

时间和空间复杂度

时间复杂度：O(n)，我们只需要遍历一次数组。
空间复杂度：O(1)，只用了常数空间来保存 maxReach。

总结

该问题通过贪心算法的方式解决，核心思想是实时更新当前能够到达的最远位置。通过一次遍历，我们可以判断是否能够到达数组的最后一个位置，确保了高效性。

45. 跳跃游戏 II

问题描述

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

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

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

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

示例 2:

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

提示:

$1 <= n u m s . l e n g t h <= 10^{4}$
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

题解

这道题的目标是找到从数组的第一个位置跳跃到最后一个位置的最小跳跃次数。每个位置的值表示从当前位置可以跳跃的最大步数。

思路

我们可以通过 贪心算法 来解决这个问题，具体的思路如下：

定义几个变量：
- jumps：记录跳跃次数。
- currentEnd：当前跳跃的最远位置，也就是说，在当前跳跃中，能跳到的最远的索引位置。
- farthest：当前跳跃中能够跳到的最远的位置。
贪心策略：
- 遍历数组，更新farthest为当前能够到达的最远位置。
- 每当遍历到currentEnd时，表示需要跳跃一次，跳到farthest的位置，并更新currentEnd。
- 如果在某次跳跃中，currentEnd已经覆盖了最后一个位置，说明已经到达了终点，直接返回跳跃次数。

代码实现

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;  // 如果数组长度为 1 或者没有跳跃，返回 0
        
        int jumps = 0;         // 跳跃次数
        int currentEnd = 0;    // 当前跳跃的结束位置
        int farthest = 0;      // 当前跳跃能到达的最远位置
        
        for (int i = 0; i < n - 1; i++) {
            farthest = max(farthest, i + nums[i]);  // 更新最远位置
            
            if (i == currentEnd) {
                jumps++;  // 跳跃一次
                currentEnd = farthest;  // 更新跳跃的目标位置
                
                if (currentEnd >= n - 1) {  // 如果当前跳跃结束后可以到达最后一个位置
                    break;
                }
            }
        }
        
        return jumps;
    }
};

int main() {
    Solution solution;
    
    // 示例 1
    vector<int> nums1 = {2, 3, 1, 1, 4};
    cout << solution.jump(nums1) << endl;  // 输出: 2
    
    // 示例 2
    vector<int> nums2 = {2, 3, 0, 1, 4};
    cout << solution.jump(nums2) << endl;  // 输出: 2
    
    return 0;
}

代码解释

初始化变量：
- jumps 用于记录跳跃次数。
- currentEnd 代表当前跳跃的结束位置。
- farthest 用于记录当前跳跃能到达的最远位置。
遍历数组：
- 对于每个位置 i，我们计算从当前位置可以跳跃到的最远位置 i + nums[i]，并更新 farthest。
- 当 i 达到 currentEnd，说明必须进行跳跃，跳到 farthest 处，并更新 currentEnd 为 farthest。
- 如果 currentEnd 已经大于或等于数组的最后一个位置，表示已经到达终点，跳出循环。
返回跳跃次数：
- 最终返回最小跳跃次数 jumps。

示例解析

示例 1

输入：

[2, 3, 1, 1, 4]

输出：

2

解释：

第 1 次跳跃：从位置 0 跳到位置 1（能跳 2 步），
第 2 次跳跃：从位置 1 跳到位置 4（能跳 3 步），到达最后一个位置。

示例 2

输入：

[2, 3, 0, 1, 4]

输出：

2

解释：

第 1 次跳跃：从位置 0 跳到位置 1，
第 2 次跳跃：从位置 1 跳到位置 4，到达最后一个位置。

边界情况

数组长度为 1：
- 如果数组长度为 1，说明我们已经在终点，跳跃次数为 0。
元素为 0：
- 题目保证能够到达最后一个位置，因此不需要额外处理无法到达的情况。

时间和空间复杂度

时间复杂度：O(n)，我们只需要遍历一次数组。
空间复杂度：O(1)，只使用了常数空间来存储几个变量。

总结

这道题通过贪心算法实现，能在遍历一次数组的同时计算出最小跳跃次数。通过更新最远跳跃的位置来减少跳跃次数，从而达到最优解。

763. 划分字母区间

问题描述

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

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

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

示例 1：

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

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

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

题解

问题分析

我们需要将字符串划分为多个片段，使得每个字母只在一个片段中出现一次，且保证将划分的所有片段按顺序连接后，结果是原始字符串。我们的任务是找出每个片段的长度。

为了做到这一点，可以利用 贪心算法 和 位置追踪 的策略。具体思路如下：

遍历字符串，记录每个字符最后出现的位置。
然后遍历字符串，尝试划分片段。在每个位置，我们会维护一个区间
1 [start, end]
，表示当前片段的左右边界。
- 如果遇到当前字符的最后位置（last_position[char]）大于 end，我们更新 end，扩展当前片段的右边界。
- 如果当前字符的索引 i 等于 end，说明当前片段已经结束，记录该片段的长度，接着处理下一个片段。

步骤

构建每个字符的最后出现位置。
贪心算法：遍历字符串，更新每个片段的最大边界。
划分并记录片段长度。

代码实现

  
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // 1. 记录每个字符最后一次出现的位置
        unordered_map<char, int> last_position;
        for (int i = 0; i < s.size(); i++) {
            last_position[s[i]] = i;
        }
        
        // 2. 贪心算法划分片段
        vector<int> result;
        int start = 0, end = 0;  // 记录当前片段的起始位置和结束位置
        
        for (int i = 0; i < s.size(); i++) {
            end = max(end, last_position[s[i]]);  // 更新片段的最远边界
            if (i == end) {  // 当前片段结束
                result.push_back(i - start + 1);
                start = i + 1;  // 更新下一片段的起始位置
            }
        }
        
        return result;
    }
};

int main() {
    Solution solution;
    
    // 示例 1
    string s1 = "ababcbacadefegdehijhklij";
    vector<int> result1 = solution.partitionLabels(s1);
    for (int len : result1) {
        cout << len << " ";
    }
    cout << endl;  // 输出: 9 7 8
    
    // 示例 2
    string s2 = "eccbbbbdec";
    vector<int> result2 = solution.partitionLabels(s2);
    for (int len : result2) {
        cout << len << " ";
    }
    cout << endl;  // 输出: 10
    
    return 0;
}

代码解释

记录字符的最后位置：
- 我们使用一个哈希表 last_position 来记录字符串中每个字符最后出现的位置。
划分片段：
- 初始化 start 和 end，表示当前片段的左右边界。
- 遍历字符串，每遇到一个字符，就更新当前片段的右边界 end，即 end = max(end, last_position[s[i]])，确保片段包括当前字符及其所有后续出现的位置。
- 当 i 达到 end 时，表示当前片段已经结束。记录当前片段的长度 i - start + 1，并更新 start 为 i + 1，开始处理下一个片段。
输出：
- 最终返回包含每个片段长度的数组。

示例解析

示例 1

输入：

s = "ababcbacadefegdehijhklij"

记录最后出现位置：

a: 8, b: 5, c: 6, d: 11, e: 14, f: 12, g: 13, h: 15, i: 17, j: 18, k: 19, l: 20

贪心划分：
- 初始 start = 0, end = 0。
- 遍历字符串并更新 end，直到我们在 i = end 位置时，完成一个片段的划分。
- 第一个片段："ababcbaca"，长度为 9。
- 第二个片段："defegde"，长度为 7。
- 第三个片段："hijhklij"，长度为 8。
输出结果：
1 [9, 7, 8]

示例 2

输入：

s = "eccbbbbdec"

记录最后出现位置：
1 e: 9, c: 7, b: 6, d: 8
贪心划分：
- 从 i = 0 开始，遍历字符串，直到我们到达 i = 9，这时整个字符串已划分为一个片段。
输出结果：
1 [10]

时间和空间复杂度

时间复杂度：O(n)，其中 n 是字符串 s 的长度。我们只遍历一次字符串来记录最后位置，并且遍历一次来划分片段。
空间复杂度：O(n)，用于存储字符的最后位置。

总结

这道题利用贪心策略，通过记录每个字符的最后出现位置，确保在划分过程中不会重复出现字符。每次处理时，我们都能有效地找到并记录当前片段的长度，最终得到正确的结果。

leetcode, hot100

本文由作者按照 CC BY 4.0 进行授权

121. 买卖股票的最佳时机

问题描述

题解

思路

代码实现

代码解释

示例解析

示例 1

示例 2

边界情况

时间和空间复杂度

总结

55. 跳跃游戏

问题描述

题解

思路

具体步骤

代码实现

代码解释

示例解析

示例 1

示例 2

边界情况

时间和空间复杂度

总结

45. 跳跃游戏 II

问题描述

题解

思路

代码实现

代码解释

示例解析

示例 1

示例 2

边界情况

时间和空间复杂度

总结

763. 划分字母区间

问题描述

题解

问题分析

步骤

代码实现

代码解释

示例解析

示例 1

示例 2

时间和空间复杂度

总结

热门标签