Leetcode编程算法随笔(难度1811 分类讨论的基础 )3738. 替换至多一个元素后最长非递减子数组1
【题目】
https://leetcode.cn/problems/longest-non-decreasing-subarray-after-replacing-at-most-one-element/description/
给你一个整数数组 nums。
你被允许最多 将数组中的一个元素替换为任何其他整数值。
返回在执行至多一次替换后，可以获得的 最长非递减子数组 的长度。
子数组是数组中的一段连续的元素序列。
如果数组中的每个元素都大于或等于其前一个元素（如果存在），则称该数组为 非递减 的。
示例 :
输入:nums = [1,2,3,1,2]
输出:4
解释:
将 nums[3] = 1 替换为 3 得到数组 [1, 2, 3, 3, 2]。
最长非递减子数组是 [1, 2, 3, 3]，其长度为 4。
# 分类讨论对这个题目写起来并不轻松 这里只是练习分类讨论的基本注意# 祛魅 前后缀分解是一种常见说法，与分解没什么关系，只是同时使用前缀和与后缀和。1.计算连续递增（递减，不增，不减）是个基本的通过O(n)时间计算的2.如果删改的化，问题就在于有没有可能将前后两个连续的子数组连接起来，什么时候可以连接，连接后的长度如何计算就是问题的关键。而这可以通过分类就可以，分类讨论的容易出现的混乱的点比较多，常见到的，分类时常通过某些条件来判断的，当条件比较多时，比如满足性质A，又满足性质B, 同时参数C要大于0...2.2. 换一个角度分类。(比如本例，用前后缀分解会更清晰）特别的，将一般情况与边界情况分开处理，很多时候归纳为更加统一的处理很费事慢一点，有时候会这样的，问题的基本思路明确了，大脑可能会放松到以为问题已经解决，“高兴的过早”并不总是坏事，大脑总要休息，总要切换模式。对于分类讨论，特别是有新概念的时候，让大脑熟悉一下，有时候是有好处的。当nums[i] >=nums[i-1] 继续将长度增加一就可以，而当遇到nums[i] < nums[i-1] 时候如何处理？会有几种情况？ // 就一种?是的😀，简单的说就是nums[i] < nums[i-1] 这一种情况
画一个辅助图，就容易看出来，还可以根据nums[i]与nums[i-2]的关系，做细分，同样的，如果有nums[i+1]，分类就会更细，不同的人，单次思考量肯定不一样，如果能直接清晰的一下分类，自然不用麻烦的去做辅助，但若一下不清楚，就慢慢来。看图，
可能会发现新的细节，就是左边的情况要不要考虑nums[i-3]...
这时候，一般不要走太远，按自己的经验，做分类的时候优先BFS 比优先DFS好,当然，根据个人习惯，只要能将类别分清晰就好。
考虑一下分类的目的，是有助于连接两个子数组(或者说和它相关)
nums[i+1]就有必要了，而这时候，有目的的分类也开始重要起来，否则种类会很多，尝试去做和连接子数组有关的分类左边的所有情况，无法通过修改红色点将左右两边连接，而右边的都可以。也容易看出关键点在于nums[i-1] 与nums[i+1]的比较，nums[i] >=nums[i-2]的情况，看起来也类似，但容易发现，特别是去考虑，它是否和连接数组有关的时候。右边的情况是可以通过调整nums[i-1]连接两个子数组的，并且这时候可以确定只要考虑nums[i-2]就可以了，nums[i] >=nums[i-2]时候 就可调整nums[i-1] 连接左右子数组，将计数继续下去nums[i+1]>=nums[i-1]时候，可调整nums[i] 将计数继续下去比如是否需要考虑nums[i+2]以及更多，可以发现不需要，修改nums[i]都可以和前面的子数组连接起来，即也可以修改nums[i-1]，使得两个元素和后面的连接起来注意，一旦出现 nums[i]<nums[i-1]，原来的修改后的子数组的连续计算，一定会被打断写代码的时候，顺便把考虑的情况作为注释写上去，写完后还可以看看是否有遗漏。
