【算法日志】贪心算法刷题：单调递增数列，贪心算法总结(day32)

代码随想录刷题60Day

---

目录

前言

单调递增数列

贪心算法总结 

---

前言

今天是贪心算法刷题的最后一天，今天本来是打算刷两道题，其中的一道hard题做了好久都没有做出来(主要思路错了)。然后再总结一下。

---

单调递增数列

   int monotoneIncreasingDigits(int n) {if (n < 10)return n;vector<int> num;int result = 0;int j = num.size() - 2, k;while (n){num.push_back(n % 10);n /= 10;}for (j = num.size() - 2,k = j + 1; j >= 0; --j){if (num[j] < num[k]){--num[k];break;}else if (num[j] > num[k])k = j;}if (j < 0) k = 0;for (int i = num.size() - 1; i >= 0; --i){if (i >= k)result = result * 10 + num[i];elseresult = result * 10 + 9;}return result;}

未解决题

贪心算法总结 

贪心算法是一种常见的算法设计技术，用于在每个步骤中做出局部最优选择，以期望达到全局最优解。下面是对贪心算法的总结：

1. 基本思想：贪心算法每次都选择当前最优的解决方案，而不考虑未来的后果。它通过贪心选择策略，在每个步骤上做出局部最优选择，以期望达到全局最优解。

2. 常规步骤：

   · 确定问题的最优子结构。
   · 构建贪心选择策略，即每一步选择局部最优解。
   · 证明贪心选择的正确性。
   · 设计递归算法或迭代算法实现贪心选择策略。
   · 分析算法的时间复杂度和空间复杂度。

3. 优点：

   · 算法简单易实现。
   · 在某些问题上能够快速得到近似最优解。
   · 时间复杂度较低，通常为线性或近似线性时间。

4. 缺点：

   · 贪心选择策略可能会导致无法达到全局最优解。
   · 对于某些问题，贪心算法不一定能给出正确的解决方案。
   · 需要证明贪心选择的正确性，有时需要较高的数学推理能力。

总的来说，贪心算法是一种简单而有效的算法设计技术，适用于满足贪心选择性质和最优子结构性质的问题。它通过每一步的局部最优选择，期望达到全局最优解。然而，贪心算法并不适用于所有问题，有时需要综合考虑其他算法技术或进行适当的修改。

---