今天是个好天气
今天是个好天气
今天是个好天气
贪心算法一般分为如下四步：
其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。
采用一个思路，小饼干喂饱小饼干的人，把大的留给胃口更大的，这样的全局思路，喂饱更多的人。
赚的是差价。
计算相邻两天的差价，如果值为正说明前一次买今天赚，计算差值序列，统计所有正值情况即可。
如果持续为正收入差价即为正值差价和，如果否则就是前面正值。
- 贪心：保证每一步尽可能走的远，并且这个题目保证可以到达最远的。
- 每次记录能到达的最远距离
- 每次选择最长的那一步，到达最长的，再走下一次最长的那一步
- 当这一步能到头，就跳出。
- next始终记录了能到达的最远距离，无论如何都包含了了终点
- DP：到达i的最少次数，等于0~i - 1的步数 + 1
- dp[i]表示到底i位置的最小步数
- 转移条件：dp[i] = min(dp[i], dp[0~i-1]) + 1
- 初始化：dp[0] = 0
- 遍历顺序，从前到后
很容易想到对负值取反，剩余的取反次数给绝对值最小的数进行操作。
这里没有想到的一个点是对nums数组的取绝对值之和，从大到小排序，这样我们能够优先对负数最小值取负变正。如果还剩余次数，对绝对值最小的取负也是影响最小的。
- 如果到达当前节点时，sum < 0，那么前面的节点也不可以。因为前面节点满足的条件是sum >=0，说明经过站点的油量至少是大于等于0的，所以肯定都不行了
- 更新答案从下一起点开始，sum重0开始。
- 没有答案：如果整体gas - cost 和小于0，从哪一个起点都不行
分两次遍历找寻答案，第一遍前序，第二遍后续。
第一遍保证右边大于左边，第二遍后续遍历才能保证可以使用之前的顺序性。
反向遍历时，保证candy[i] > candy[ i + 1], 取 candy [i] = max(candy[i], candy [ i + 1] + 1), 这样也能保证前序的大小关系。
插入[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]]
维护一个最小的边界，每次更新这个边界，超过这个边界就 + 1
计算去除交叉区间 == 总区间 - 计算不交叉区间
计算不交叉区间，考虑排序判断边界，这里考虑右边界排序，然后从左向右遍历，选择左边界尽可能小的，腾出空间给后面的。
- 记录每个字母的最远位置，作为一个分割点
- 遍历每个位置，当前字母的最远位置与当前位置重合，划分为一个区间。
能想到一位位判断每个位置的数，但是剩下的就一头雾水了。
题解是从后向前判断数字的递增性，如果strNum[i - 1] > strNum[i]的话，就strNum[i - 1] - 1,而 strNum[i] 一维置 9。先把递增行维护好，最后一次性置9.
这里有两个重要的函数，stoi和to_string。
每次看贪心题目都觉得自己是笨比。