738. 单调递增的数字
1. 思路
从后向前判断，如果不呈现单调递增的状态，后一位变成9，前一位-1。这里局部最优是每两位的最优解，从后向前线性遍历能得到全局最优。
但是有一点没有想清楚。如果出现了上述的两位数倒序情况，之后的所有数字都应该变成9。例如52583，最小的递增数是49999。中间三位其实是递增的，但是在52调整成49后，后续的所有数都应该是9，因此应该是在从头开始最先出现倒序之后全部调整成9。
方法是记录flag。flag对于多重线性完成的任务有效果，先记录，最后再遍历一遍完成调整。
至于为什么从头开始最先出现倒序但不从头开始遍历，就是因为调整的过程依赖于后面的数字（如果倒序，前一位-1），因此必须从后向前遍历。
2. 方法
巧用to_string和stoi，并且，因为整数str的asc码也是连续的，因此'9'-1 = ‘8’。
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);
}
};
968. 监控二叉树
1. 思路
本题的核心思路为，从叶子到源头进行二叉树搜索，满足下面的尽量不放摄像头这个原则。回溯至源头后，摄像头的个数就是最少的。严格的数学证明有些困难，也不必要。
如何判断是否该放置摄像头，可以通过叶子的状态来判断。分别是：
1-有摄像头，2-有覆盖，0-没有覆盖
（1）如果孩子都有覆盖，不放摄像头。注意它的前提是，可以被再往上的摄像头覆盖。因此头节点可能因为这种情况而丢失覆盖，因为没有再往上的节点了。因此，需要最后判断头节点有没有被覆盖。
（2）如果有一个孩子没有覆盖，放摄像头。
（3）如果有一个孩子有摄像头，不放摄像头，但改成被覆盖。
最后，叶子之下的空节点，由于不想让叶子被放摄像头，呈现没有被覆盖但没有摄像头的状态，因此将空节点调成全部被覆盖。注意不能在叶子节点下面放摄像头，因为想让叶子呈现空状态。
class Solution {
public:
int result;
int traversal(TreeNode* cur){
if(cur==NULL) return 2;
int left = traversal(cur->left);
int right = traversal(cur->right);
// 左右孩子都有覆盖
if (left==2 && right==2){
return 0;
}
// 左右孩子有一个没有覆盖，放摄像头
if (left==0 || right==0){
result++;
return 1;
}
// 左右孩子有一个摄像头，不放
if (left==1 || right==1){
return 2;
}
return -1;
}
int minCameraCover(TreeNode* root) {
result = 0;
if (traversal(root) == 0) { // root 无覆盖
result++;
}
return result;
}
};