贵阳网站建设制作,荥阳网,个人卖货平台,珠海酒店网站建设一、LeetCode 738.单调递增的数字 题目链接/文章讲解/视频讲解#xff1a;https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html 状态#xff1a;已解决 1.思路 如何求得小于等于N的最大单调递增的整数#xff1f;98https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html 状态已解决 1.思路 如何求得小于等于N的最大单调递增的整数98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]--然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。也就是说我们只需要找到最先不满足单增性质的位置然后将前一个元素-1后面的所有元素变为9即可。因此代码分两步
1找到整数中最先不满足单增性质的前后元素 遍历数组比较前后两个元素的大小然后不断维护前者大于后者的最新下标。此时是从前向后遍历还是从后向前遍历呢从前向后遍历的话遇到strNum[i - 1] strNum[i]的情况让strNum[i - 1]减一但此时如果strNum[i - 1]减一了可能又小于strNum[i - 2]。这么说有点抽象举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299。
2后面所有元素变为9 从维护的位置开始到整数末每个数都变为9。
2.代码实现
class Solution {
public:int monotoneIncreasingDigits(int n) {string s to_string(n);int pos s.size();//注意初值值设为数组末以便找不到不符合单增性质的位置时//让第二个循环不做for(int is.size()-1;i0;i--){if(s[i-1] s[i]){s[i-1]--;pos i;}}for(int ipos;is.size();i){s[i] 9;}return stoi(s);}
};
二、总结
1.贪心简单题 以下三道题目就是简单题可以初步理解贪心的概念。
贪心算法分发饼干(opens new window)贪心算法K次取反后最大化的数组和(opens new window)贪心算法柠檬水找零
2.贪心中等题
1这两类属于第一次接触较为难想的题偏数学。
贪心算法摆动序列(opens new window)贪心算法单调递增的数字
2贪心解决股票问题 一般的股票问题是动规的领域但部分用贪心也可以解决以下是比较经典的两道可以贪心完成的股票问题。
贪心算法买卖股票的最佳时机II(opens new window)贪心算法买卖股票的最佳时机含手续费 (opens new window)本题使用贪心算法比较绕建议后面学习动态规划章节的时候理解动规就好
3两个维度的题 在出现两个维度相互影响的情况时两边一起考虑一定会顾此失彼要先确定一个维度再确定另一个一个维度。
贪心算法分发糖果(opens new window)贪心算法根据身高重建队列
3.贪心难题
1贪心解决区间问题 主要是一些区间覆盖问题如何统计如何去除。
贪心算法跳跃游戏(opens new window)贪心算法跳跃游戏II(opens new window)贪心算法用最少数量的箭引爆气球(opens new window)贪心算法无重叠区间(opens new window)贪心算法划分字母区间(opens new window)贪心算法合并区间
2无规律的题
贪心算法最大子序和 (opens new window)
贪心算法加油站 (opens new window)
4.总览
