做移动网站设计,广西住房建设厅网站,网站建设员工分工,汕头网站建设托管文档讲解#xff1a;单调递增的数字 监控二叉树 贪心算法总结 738.单调递增的数字
题目链接#xff1a;https://leetcode.cn/problems/monotone-increasing-digits/description/
思路#xff1a; 题目要求小于等于N的最大单调递增的整数#xff0c;那么拿一个两位的数字… 文档讲解单调递增的数字 监控二叉树 贪心算法总结 738.单调递增的数字
题目链接https://leetcode.cn/problems/monotone-increasing-digits/description/
思路 题目要求小于等于N的最大单调递增的整数那么拿一个两位的数字来举例。 例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]--然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。 这一点如果想清楚了这道题就好办了。 此时是从前向后遍历还是从后向前遍历呢 从前向后遍历的话遇到strNum[i - 1] strNum[i]的情况让strNum[i - 1]减一但此时如果strNum[i - 1]减一了可能又小于strNum[i - 2]。 这么说有点抽象举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。 那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299
核心代码
class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum to_string(N);int flag strNum.size();for (int i strNum.size() - 1; i 0; i--) {if (strNum[i - 1] strNum[i] ) {flag i;strNum[i - 1]--;}}for (int i flag; i strNum.size(); i) {strNum[i] 9;}return stoi(strNum);}
};
今日总结 今日学习时长2h第二题看题解能看明白但写不出来后面再补题吧。
