2024.7.10 刷题总结

2024.7.10

**每日一题**

2970.统计移除递增子数组的数目 Ⅰ，这道题是一个考察双指针的题目，也考察了数组的基本性质。题目的意思是要统计有多少个子数组能满足移除后剩下的元素为严格递增的关系，刚开始没考虑到移除的元素要是连续的，所以出错了。考虑到这个问题之后，我们可以分类来讨论;首先，我们可以先统计一下数组的最大前缀， 如果整个数组都是递增的，那么我们就不用再算其他情况了;如果不是，那我们就先加上只考虑所有递增前缀的答案，是最大递增前缀的下标加2;然后我们再考虑一般情况，即移除中间数组，这样的情况会造成一个递增前缀和一个递增后缀，且连接处前面的小于后面的。对于这种两边都需要枚举讨论的题目，我们可以只枚举一边，然后判断另外一边的数值，所以我们选择枚举后缀，只要后缀满足往前递减的关系，我们就进行计算，我们先让最大递增前缀往回，直到连接处满足关系，然后此时答案就是最大前缀的下标加2，剩下的任务就是模仿这个过程完成循环，直到后缀不满足情况就结束。

63.不同路径 Ⅱ，这道题是一道简单动态规划题目，主要目的是训练我们的DP思想。根据题意，机器人往右走或者往下走，所以每一步的方法数是上面一步的方法数加上左边一步的方法数。但是我们注意到有障碍物，所以当遇到障碍物时，我们令其的总方法数为0即可。本题还需要进行初始化，先判断起点，然后再初始化第一排和第一列，初始化也需要判断障碍物。