贪心type
status
date
slug
summary
tags
category
icon
password
Property
贪心算法（greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。
核心思想：将求解过程分成「若干个步骤」，然后根据题意选择一种「度量标准」，每个步骤都应用「贪心原则」，选取当前状态下「最好 / 最优选择（局部最优解）」，并以此希望最后得出的结果也是「最好 / 最优结果（全局最优解）」。
对许多问题来说，可以使用贪心算法，通过局部最优解而得到整体最优解或者是整体最优解的近似解。但并不是所有问题，都可以使用贪心算法的。一般来说，这些能够使用贪心算法解决的问题必须满足下面的两个特征：
- 贪心选择性质
贪心选择指的是一个问题的全局最优解可以通过一系列局部最优解（贪心选择）来得到。当进行选择时，直接做出在当前问题中看来最优的选择，而不用去考虑子问题的解。在做出选择之后，才会去求解剩下的子问题
贪心算法在进行选择时，可能会依赖之前做出的选择，但不会依赖任何将来的选择或是子问题的解。运用贪心算法解决的问题在程序的运行过程中无回溯过程。
- 最优子结构
最优子结构指的是一个问题的最优解包含其子问题的最优解
举个例子，如下图所示，原问题，在步通过贪心选择选出一个当前最优解之后，问题就转换为求解子问题。如果原问题的最优解可以由「第步通过贪心选择的局部最优解」和「的最优解」构成，则说明该问题满足最优子结构性质。
也就是说，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。
证明
贪心算法有两种证明方法：反证法和归纳法
- 反证法：从最优解出发，在保证全局最优不变的前提下，如果交换方案中任意两个元素 / 相邻的两个元素后，答案不会变得更好，则可以推定目前的解是最优解。
- 归纳法：先算得出边界情况（例如）的最优解 ，然后再证明：对于每个，都可以由推导出结果。
分发饼干
题目：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子
i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。示例：
为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。证明如下。
假设有个孩子，胃口值分别是到，有块饼干，尺寸分别是到，满足和，其中，。
假设在对前 个孩子分配饼干之后，可以满足第个孩子的胃口的最小的饼干是第块饼干，即是剩下的饼干中满足的最小值，最优解是将第块饼干分配给第个孩子。如果不这样分配，考虑如下两种情形：
- 如果 且也成立，则如果将第 块饼干分配给第 个孩子，且还有剩余的饼干，则可以将第 块饼干分配给第个孩子，分配的结果不会让更多的孩子被满足；
- 如果，则如果将第块饼干分配给第个孩子，当时，可以将第块饼干分配给第个孩子，分配的结果不会让更多的孩子被满足；当时，第 块饼干无法分配给任何孩子，因此剩下的可用的饼干少了一块，因此分配的结果不会让更多的孩子被满足，甚至可能因为少了一块可用的饼干而导致更少的孩子被满足。
基于上述分析，可以使用贪心的方法尽可能满足最多数量的孩子。
分发糖果
题目：
n个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。需要按照以下要求，给这些孩子分发糖果：- 每个孩子至少分配到
1个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例：
先确定右边评分大于左边的情况（也就是从前向后遍历）
此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
如果
ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1再确定左孩子大于右孩子的情况（从后向前遍历）
如果
ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。那么又要贪心了，局部最优：取
candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。局部最优可以推出全局最优。
买卖股票的最佳时机 II
题目：给一个整数数组
prices ，其中prices[i]表示某支股票第i天的价格。在每一天，可以决定是否购买和/或出售股票。在任何时候最多只能持有一股股票。也可以先购买，然后在同一天出售。返回你能获得的最大利润示例：
由于股票的购买没有限制，因此整个问题等价于寻找个不相交的区间 使得等式最大化
其中表示在第天买入， 表示在第 天卖出。
同时对于 这一个区间贡献的价值 ，其实等价于 这若干个区间长度为1的区间的价值和，因此问题可以简化为找 x个长度为1的区间 使得价值最大化。
贪心的角度考虑每次选择贡献大于0的区间即能使得答案最大化，因此最后答案为
跳跃游戏
题目：给定一个非负整数数组
nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。示例：
对于数组中的任意一个位置 ，如何判断它是否可以到达？只要存在一个位置 ，它本身可以到达，并且它跳跃的最大长度大于等于，即，那么位置 也可以到达。
对于每一个可以到达的位置 ，它使得这些连续的位置都可以到达。
这样以来，依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置 ，如果它在最远可以到达的位置的范围内，那么就可以从起点通过若干次跳跃到达该位置，因此可以用 更新最远可以到达的位置。
在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，就可以直接返回 True 。
移掉 K 位数字
题目：给一个以字符串表示的非负整数
num 和一个整数 k ，移除这个数中的k位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。示例：
要让剩下数字最小，就要保证靠前的数字尽可能小（贪心）。比如425，要删去4，也就是说看到从左到右有递减的序列，就要删掉左边的大数字；如果没有这样的序列，比如是245，那就删除最后一个数字
- 基于上述思路，先删掉左边的大数字，每次删去一个字符后，剩下的个长度的序列就形成新的子问题，继续用同样方法，直至删次。可以用单调非严格递增栈来找寻下一个更小的数字。对于每个数字，如果该数字小于栈顶元素，就不断弹出栈顶元素，也就是删除左边大的元素，直到空栈或新的栈顶元素不大于当前数字或已经删除k次，就停止删除左边的大数字
- 当栈空，且遍历到的数字为'0'时，由于除了0之外没有前导0，所以这个'0'要直接跳过
- 第一步完成后，如果k还大于0且栈非空，那就删除右边的数字，也就是最后的数字
- 如果栈为空，返回"0"，否则就返回栈
最大交换
题目：给定一个非负整数，至多可以交换一次数字中的任意两位。返回你能得到的最大值
示例：
从左向右遍历每个数字（转化成string方便处理） 对于每个数字，在其右侧的数字中，贪心地找到 最大的（多个最大值取最靠后的）数字替换即可（最大数字应满足比当前数字大） 找到后直接返回即可
加油站
题目：在一条环路上有
n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。给定两个整数数组 gas 和 cost ，如果可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。示例：
如果总油量减去总消耗大于等于零那么一定可以跑完一圈，因此要跑完一圈就要保证在各个站点的加油站 剩油量
rest[i] >= 0。 局部最优：若当前累加到 的和，起始位置至少要是 ，因为从开始一定不行。 全局最优：找到可以跑一圈的起始位置。
- 遍历数组 从 开始累加
rest[i]，和记为curSum
- 计算每个加油站的剩余量
curSum += gas[i] - cost[i]
- 若
curSum小于零，说明[0,i]区间都不能作为起始位置，起始位置从i+1算起，curSum清零重新计算
跳跃游戏 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]。示例：
