第10章 贪心算法
贪心没有固定的模板套路
如果找出局部最优并可以推出全局最优，就是贪心；如果局部最优都没有找出来，就不是贪心，可能是单纯的模拟。
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
455. 分发饼干【简单】
思路：小饼干给小胃口
同样可以反过来，大饼干给大胃口
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int j = 0; //定位g，即胃口 这里必须初始化，要不然报错
for(int i = 0; i < s.size(); i++) { //遍历饼干
if(j < g.size() && s[i] >= g[j]) { //前面的判断条件防止超出索引
j++;
}
}
return j; //索引就是人数
}
};
376. 摆动序列【中等】
题目意思：就是找极大极小值的个数
- 思路一：贪心
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
int preDiff = nums[1] - nums[0];
int res = preDiff != 0 ? 2 : 1;
for(int i = 2; i < nums.size(); ++i){
int curDiff = nums[i] - nums[i-1];
//出现峰值
if((preDiff<=0 && curDiff>0) || (preDiff>=0 && curDiff<0)){
res++;
preDiff = curDiff;
}
}
return res;
}
};
思路二：动态规划
53. 最大子数组和【简单】
思路一：双for循环暴力破解：计算从每一个索引开始的最大子序和
//两for循环暴力破解
//计算从索引0开始的的最大子字符串， 从1开始， 从2开始......
//时间复杂度：O(n^2)， 超出时间限制的
class Solution
{
public:
int maxSubArray(vector<int>& nums){
//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小值 或 最大值
int sumMax = INT_MIN;
for (int i = 0; i < nums.size(); i++){
int sum = 0;
for (int j = i; j < nums.size(); j++){
sum += nums[j];
sumMax = max(sum, sumMax);
}
}
return sumMax;
}
};
思路二：动态规划
思路可查看此人的PPT：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//先替换元素 更新数组
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] > 0) { //如果前一个元素>0 后一个元素改为两者之和
nums[i] = nums[i - 1] + nums[i];
}
}
//再遍历查找最大值
int res = nums[0];
for (int i : nums) {
res = max(res, i);
}
return res;
}
};
我们可以对两个并行for循环进行优化，只用一个for循环解决
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] > 0) {
nums[i] = nums[i - 1] + nums[i];
}
if (nums[i] > res) {
res = nums[i];
}
}
return res;
}
};
接着优化缩短代码，往官方参考答案靠近
- [x]
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = nums[0];
for (int i = 1; i < nums.size(); i++) {
nums[i] = max(nums[i], nums[i - 1] + nums[i]); //主要是这句代码
res = max(res, nums[i]); //动态记录最大子序和
}
return res;
}
};
代码随想录动态规划的思路：
五部曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size());
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
res = max(dp[i], res); // res 保存dp[i]的最大值
}
return res;
}
};
- 思路三：贪心
时间复杂度：O(n)
空间复杂度：O(1)
思路查看：https://leetcode-cn.com/problems/maximum-subarray/solution/dai-ma-sui-xiang-lu-53-zui-da-zi-xu-he-b-8d7l/
贪心贪的是哪里呢？
如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
class Solution{
public:
int maxSubArray(vector<int>& nums){
//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
int res = INT_MIN;
int sum = 0;
for (int i = 0; i < nums.size(); i++){
sum += nums[i];
res = max(res, sum);
//如果sum < 0，重新开始找子序串
if (sum < 0){
sum = 0;
}
}
return res;
}
};
1005. K 次取反后最大化的数组和【简单】
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int nums_min = INT_MAX;
int res = 0;
for(int i = 0; i < nums.size(); i++){
if(k > 0 && nums[i] < 0){
nums[i] = -nums[i];
k--;
}
res += nums[i];
nums_min = min(nums_min, nums[i]);
}
if(k % 2 == 0) return res;
else return res - 2*nums_min;
}
};
- 主要会写绝对值排序就行
class Solution {
static bool cmp(int a, int b) { //绝对值从大到小排序
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), cmp); // 第一步：以绝对值大小排序，从大到小
for (int i = 0; i < nums.size(); i++) { // 第二步：-改+
if (nums[i] < 0 && k > 0) {
nums[i] = -nums[i];
k--;
}
}
if (k % 2 == 1) nums[nums.size() - 1] *= -1; // 第三步：k还有多，看是否需要修改最小值的正负号
int res = 0;
for (int num : nums) res += num; // 第四步：收集
return res;
}
};
134. 加油站【中等】
思路一：暴力破解
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
for (int i = 0; i < cost.size(); i++) {
int rest = gas[i] - cost[i]; // 记录剩余油量
if (rest < 0) continue;
int index = (i + 1) % cost.size(); //下一个加油站的索引
while (rest >= 0 && index != i) { // 模拟以i为起点行驶一圈
rest += gas[index] - cost[index];
index = (index + 1) % cost.size();
}
// 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置
if (rest >= 0 && index == i) return i;
}
return -1;
}
};
思路二：贪心
- 情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
- 情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
- 情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int minSum = INT_MAX; // 从起点出发，油箱里的油量最小值
for (int i = 0; i < gas.size(); i++) {
int rest = gas[i] - cost[i];
curSum += rest;
minSum = min(minSum, curSum);
}
if (curSum < 0) return -1; // 情况1
if (min >= 0) return 0; // 情况2
// 情况3
for (int i = gas.size() - 1; i >= 0; i--) {
int rest = gas[i] - cost[i];
min += rest;
if (min >= 0) {
return i;
}
}
return -1;
}
};
- 思路三：贪心方法二
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int totalSum = 0; //跑完整圈后的剩余油量
int start = 0;
for (int i = 0; i < gas.size(); i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 0; // curSum从0开始
}
}
if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
else return start;
}
};
860. 柠檬水找零【简单】
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int money[2] = {0,0}; //分别记录5,10元钞票多少张
for(auto bill : bills){
if(bill == 5){
money[0]++;
}
else if(bill == 10){
money[0]--;
money[1]++;
if(money[0] < 0) return false;
}
else if(bill == 20){
if(money[1] > 0){ //有10元的钞票，找零1张5元、1张10元
money[1]--;
money[0]--;
}
else{
money[0] -= 3; //没有10元的，则找零3张5元
}
if(money[0] < 0) return false;
}
}
return true;
}
};
452. 用最少数量的箭引爆气球【中等】
- 以左边界排序，从小到大
class Solution {
private:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int res = 1; // points 不为空至少需要一支箭
for (int i = 1; i < points.size(); i++) { //两个气球及以上跑这里
if (points[i][0] > points[i - 1][1]) { // 气球i和气球i-1不挨着，注意这里不是>=
res++; // 需要一支箭
}
else { // 气球i和气球i-1挨着
points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界 关键代码
}
}
return res;
}
};
- 时间复杂度：O(n\log n)，因为有一个快排
- 空间复杂度：O(1)
435. 无重叠区间【中等】
思路：统计无重叠区间个数，再总个数减一下就是result
以右边界排序
class Solution {
public:
// 按照区间右边界排序
static bool cmp (const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
//if (intervals.size() == 0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int count = 1; // 记录非交叉区间的个数
int end = intervals[0][1]; // 记录区间分割点
for (int i = 1; i < intervals.size(); i++) { //计算有几个无重叠区间
if (end <= intervals[i][0]) {
end = intervals[i][1];
count++;
}
}
return intervals.size() - count;
}
};
- 时间复杂度：O(n\log n) ，有一个快排
- 空间复杂度：O(1)
763. 划分字母区间【中等】
必须两次遍历：第一次遍历更新索引，第二次遍历收集结果
class Solution {
public:
vector<int> partitionLabels(string s) {
int hash[26] = {0}; //存储 字符对应的最后索引
for(int i = 0; i < s.size(); i++){ //统计每一个字符最后出现的位置
hash[s[i] - 'a'] = i;
}
int right = 0; //每个子串的开始和结束索引
int left = 0;
vector<int> res;
for(int i = 0; i < s.size(); i++){
right = max(right, hash[s[right] - 'a']); // 找到字符出现的最远边界 这句代码很重要
if(i == right){
res.push_back(right - left + 1);
left = right + 1;
}
}
return res;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)，使用的hash数组是固定大小
56. 合并区间【中等】
自己写的：
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b){
if(a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size() == 1) return intervals; //1.处理size==1的情况
sort(intervals.begin(), intervals.end(), cmp); //2.排序
vector<vector<int>> res;
for(int i = 1; i < intervals.size(); ++i){
if(intervals[i][0] <= intervals[i-1][1]){ //核心代码
intervals[i][0] = intervals[i-1][0];
intervals[i][1] = max(intervals[i-1][1], intervals[i][1]);
intervals[i-1][1] = -1;
}
else{
res.push_back(intervals[i-1]);
}
}
//处理最后一个
if(intervals[intervals.size()-1][0] > intervals[intervals.size()-2][1]){
res.push_back(intervals[intervals.size()-1]);
}
return res;
}
};
- 官方答案
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() < 2) return intervals;
// 排序的参数使用了lamda表达式
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
vector<vector<int>> res;
res.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (res.back()[1] >= intervals[i][0]) { // 合并区间
res.back()[1] = max(res.back()[1], intervals[i][1]); //这里实现合并
}
else {
res.push_back(intervals[i]);
}
}
return res;
}
};
- 时间复杂度：O(n\log n)，有一个快排
- 空间复杂度：O(1)，我没有算result数组（返回值所需容器占的空间
738. 单调递增的数字【中等】
思路一：暴力破解
一个一个减1判断是否满足条件
class Solution {
//暴力破解
//时间复杂度：O(nm) m为n的数字长度
//空间复杂度：O(1)
public:
bool checkNum(int num) {
int low_pos = 10; //记录最低位
while (num) {
int temp_pos = num % 10; //拿出最低位
if (low_pos >= temp_pos) low_pos = temp_pos; //最低位大于次低位 更新最低位
else return false; //如果低位比高位小 false
num = num / 10;
}
return true;
}
int monotoneIncreasingDigits(int N) {
for (int i = N; i > 0; i--) { //一个一个判断
if (checkNum(i)) return i;
}
return 0;
}
};
- 思路二：贪心
class Solution {
public:
int monotoneIncreasingDigits(int N) {
string strNum = to_string(N); //数字转字符串 string头文件的函数
//1.找到标记位置，并使标记位的前一位-1
int flag = strNum.size();
for (int i = strNum.size() - 1; i > 0; i--) { //必须从后面遍历到前面 反过来实现不了
if (strNum[i - 1] > strNum[i]) { //前一位>后一位
flag = i; //后一位改9
strNum[i - 1]--; //前一位减1 332 -> 322 -> 222
}
}
//2.标记位起改9
for (int i = flag; i < strNum.size(); i++) { //标记位置开始改9
strNum[i] = '9'; //222 -> 299
}
return stoi(strNum); //字符串转数字
}
};
- 时间复杂度：O(n)，n 为数字长度
- 空间复杂度：O(n)，需要一个字符串，转化为字符串操作更方便
968. 监控二叉树【困难，不会】
有如下三种：
- 该节点无覆盖
- 本节点有摄像头
- 本节点有覆盖
我们分别有三个数字来表示：
- 0：该节点无覆盖
- 1：本节点有摄像头
- 2：本节点有覆盖
可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。
单层逻辑处理，主要有如下四类情况：
- 情况1：左右节点都有覆盖
- 左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
- 情况2：左右节点至少有一个无覆盖的情况
- 如果是以下情况，则中间节点（父节点）应该放摄像头
- 情况3：左右节点至少有一个有摄像头
- 如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）
- 情况4：头结点没有覆盖
// 版本一
class Solution {
private:
int result;
int traversal(TreeNode* cur) {
// 空节点，该节点有覆盖
if (cur == NULL) return 2;
int left = traversal(cur->left); // 左
int right = traversal(cur->right); // 右
// 情况1
// 左右节点都有覆盖
if (left == 2 && right == 2) return 0;
// 情况2
// left == 0 && right == 0 左右节点无覆盖
// left == 1 && right == 0 左节点有摄像头，右节点无覆盖
// left == 0 && right == 1 左节点有无覆盖，右节点摄像头
// left == 0 && right == 2 左节点无覆盖，右节点覆盖
// left == 2 && right == 0 左节点覆盖，右节点无覆盖
if (left == 0 || right == 0) {
result++;
return 1;
}
// 情况3
// left == 1 && right == 2 左节点有摄像头，右节点有覆盖
// left == 2 && right == 1 左节点有覆盖，右节点有摄像头
// left == 1 && right == 1 左右节点都有摄像头
// 其他情况前段代码均已覆盖
if (left == 1 || right == 1) return 2;
// 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
// 这个 return -1 逻辑不会走到这里。
return -1;
}
public:
int minCameraCover(TreeNode* root) {
result = 0;
// 情况4
if (traversal(root) == 0) { // root 无覆盖
result++;
}
return result;
}
};
跳跃游戏
55. 跳跃游戏【中等】
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() < 2) return true; // 只有0,1个元素，就是能达到
int cover = 0;
for (int i = 0; i < nums.size(); i++) {
if(i <= cover){ //i在覆盖范围内
cover = max(i + nums[i], cover); //更新覆盖范围
if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
}
else return false;
}
return false; //这句走不到
}
};
45. 跳跃游戏 II【中等】
题目意思：最少的次数到达最后位置，假设总能到达最后位置
从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。
这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时
- 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
- 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() < 2) return 0;
int curDistance = 0; // 当前覆盖最远距离下标
int ans = 0; // 记录走的最大步数
int nextDistance = 0; // 下一步覆盖最远距离下标
for (int i = 0; i < nums.size(); i++) {
nextDistance = max(nums[i] + i, nextDistance); // 记录下一步覆盖最远距离下标
if (i == curDistance) { // 遇到当前覆盖最远距离下标
if (curDistance < nums.size() - 1) { // 如果当前覆盖最远距离下标不是终点
ans++; // 需要走下一步
curDistance = nextDistance; // 更新当前覆盖最远距离下标（相当于加油了）
if (nextDistance >= nums.size() - 1) break; // 下一步的覆盖范围已经可以达到终点，结束循环
}
else break; // 当前覆盖最远距离下标是集合终点，不用做ans++操作了，直接结束
}
}
return ans;
}
};
在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
- [x]
class Solution {
public:
int jump(vector<int>& nums) {
int curDistance = 0; // 当前覆盖的最远距离下标
int ans = 0; // 记录走的最大步数
int nextDistance = 0; // 下一步覆盖的最远距离下标
for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在
nextDistance = max(nums[i] + i, nextDistance); // 记录下一步覆盖的最远距离下标
if (i == curDistance) { // 遇到当前覆盖的最远距离下标
curDistance = nextDistance; // 更新当前覆盖的最远距离下标
ans++;
}
}
return ans;
}
};
两个维度权衡问题
135. 分发糖果【困难】
- 思路一：贪心
时间复杂度：O(n)
空间复杂度：O(n)
两次遍历，一次向后，一次向前
class Solution {
public:
int candy(vector<int>& ratings) {
//1. 分发糖果
vector<int> candyVec(ratings.size(), 1); //1.1 先每人分一个
// 从前向后
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) { //1.2 右边的比左边多一个
candyVec[i] = candyVec[i - 1] + 1;
}
}
// 从后向前
for (int i = ratings.size() - 2; i >= 0; i--) { //确定左边>右边
if (ratings[i] > ratings[i + 1] ) {
candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1); //选取max是因为要保持上面的不变
}
}
// 2. 统计结果
int res = 0;
for (int i = 0; i < candyVec.size(); i++) {
res += candyVec[i];
}
return res;
}
};
方法二：常数空间遍历
时间复杂度：O(n)
空间复杂度：O(1)
https://leetcode-cn.com/problems/candy/solution/fen-fa-tang-guo-by-leetcode-solution-f01p/
class Solution {
public:
int candy(vector<int>& ratings) {
int res = 1;
int inc = 1; //最近递增序列长度
int dec = 0; //当前递减序列长度
int pre = 1; //前一个同学的苹果数量
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] >= ratings[i - 1]) {
dec = 0;
pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1;
res += pre;
inc = pre;
}
else {
dec++;
if (dec == inc) {
dec++;
}
res += dec;
pre = 1;
}
}
return res;
}
};
406. 根据身高重建队列【中等】
思路：先排序，后插入
插入的过程：
-
插入[7,0]：[[7,0]]
-
插入[7,1]：[[7,0],[7,1]]
-
插入[6,1]：[[7,0],[6,1],[7,1]]
-
插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
-
插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
-
插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
-
时间复杂度：O(n\log n + n^2)
-
空间复杂度：O(n)
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort (people.begin(), people.end(), cmp); //1.排序 高->低
vector<vector<int>> que;
for (int i = 0; i < people.size(); i++) {
int position = people[i][1];
que.insert(que.begin() + position, people[i]); //2.插序
}
return que;
}
};
但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。
- [x]
class Solution {
public:
// 身高从大到小排（身高相同k小的站前面）
static bool cmp(const vector<int>& a, const vector<int>& b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort (people.begin(), people.end(), cmp);
list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多
for (int i = 0; i < people.size(); i++) {
int position = people[i][1]; // 插入到下标为position的位置
list<vector<int>>::iterator it = que.begin();
while (position--) { // 寻找在插入位置
it++;
}
que.insert(it, people[i]); //链表的插入速度快
}
return vector<vector<int>>(que.begin(), que.end()); //list容器->vector容器
}
};
该方法速度更快，但是以空间换取时间
动态数组底层会进行全量拷贝扩容，所以消耗时间
股票系列
121. 买卖股票的最佳时机【简单】
相同题目：剑指 Offer 63. 股票的最大利润
题目意思：只能买入一次，卖出一次，最大利润
思路一：双for暴力破解；思路和53.最大子序和很像
时间复杂度：O(n^2)
空间复杂度：O(1)
class Solution {
public:
//双for循环暴力破解 超出时间限制
int maxProfit(vector<int>& prices) {
int max_fit = 0;
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
max_fit = max(max_fit, prices[j] - prices[i]);
}
}
return max_fit;
}
};
- 思路二：贪心
股票，去数组左边的最小值，右边的最大值，差值即为最大利润
时间复杂度：O(n) 一次for循环遍历
空间复杂度：O(1)
思路可查看代码随想录的：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/dai-ma-sui-xiang-lu-121-mai-mai-gu-piao-odhle/
class Solution {
public:
int maxProfit(vector<int>& prices) {
int low = INT_MAX;
int res = 0;
for (int i = 0; i < prices.size(); i++) { //从左到右遍历
low = min(low, prices[i]); // 动态更新最小价格
res = max(res, prices[i] - low); // 动态更新最大利润
}
return res;
}
};
思路三：动态规划
有点难，下次再来补充
122. 买卖股票的最佳时机 II【中等】
题目意思：
- 只有一只股票！
- 当前只有买股票或者买股票的操作
思路：把每一题的股价描点画成折线图，求所有上升线段的累加；借鉴376题
- 贪心：
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for(int i = 1; i < prices.size(); i++){
res += max(0, prices[i]-prices[i-1]);
}
return res;
}
};
714. 买卖股票的最佳时机含手续费【中等，不会】
-
思路一：贪心
-
时间复杂度：O(n)
-
空间复杂度：O(1)
我们在做收获利润操作的时候其实有三种情况：
- 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
- 情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
- 情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int res = 0;
int minPrice = prices[0]; // 记录最低价格
for (int i = 1; i < prices.size(); i++) {
// 情况二：相当于买入
if (prices[i] < minPrice) minPrice = prices[i];
// 情况三：保持原有状态（因为此时买则不便宜，卖则亏本）
//if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
// continue;
//}
// 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出
if (prices[i] > minPrice + fee) {
res += prices[i] - minPrice - fee;
minPrice = prices[i] - fee; // 情况一，这一步很关键
}
}
return res;
}
};
当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利
- [x]
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int buy = prices[0] + fee;
int profit = 0;
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] + fee < buy) { //更新买入价
buy = prices[i] + fee;
}
else if (prices[i] > buy) { //收集利润
profit += prices[i] - buy;
buy = prices[i];
}
}
return profit;
}
};
思路二：动态规划