贪心算法：基础

睡不醒的鲤鱼 2021-12-19 每日一题 LeetCode

# 0045. 跳跃游戏 II (opens new window)

题目

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

解析

贪心地进行正向查找，每次找到可到达的最远位置，将其设为当前跳跃区间右边界，累加步数的时机就是到达右边界，需要再次起跳。

代码

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0;  // 当前能走到的最远位置
        int end = 0;  // 上次跳跃可达范围右边界
        int ans = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            maxPos = max(maxPos, nums[i] + i);
            // 已到达上次跳跃可达范围右边界，需要再次起跳
            if (i == end) {
                end = maxPos;
                ans++;
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 0055. 跳跃游戏 (opens new window)

题目

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

解析

遍历数组的同时维护一个当时能走到的最远位置，若不能到达此时下标，则说明不能到达最后一个下标，直接返回即可。

代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        for (int i = 0, maxPos = 0; i < nums.size(); i++) {
            if (i > maxPos) return false;
            maxPos = max(maxPos, i + nums[i]);
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10

# 0122. 买卖股票的最佳时机 II (opens new window)

题目

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润。

解析

将每个价格上升的子区间相加即可。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for (int i = 1; i < prices.size(); i++) {
            ans += max(prices[i] - prices[i - 1], 0);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10

# 0135. 分发糖果 (opens new window)

题目

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

解析

根据每个孩子左（右）侧比当前孩子得分低的相邻单调递增（减）区间内的孩子数量，确定能分配的最少糖果数量，最后累加即可。

代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> left(n), right(n);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += max(left[i], right[i]) + 1;
        }
        return ans;
    }
};