@ninijia 在 Leetcode每日一题练习 ------ 1574. 删除最短的子数组使剩余数组有序 中发帖
从Leetcode 每日一题练习继续讨论:
1574. 删除最短的子数组使剩余数组有序
1574. Shortest Subarray to be Removed to Make Array Sorted
题解
本题需要移除一个子数组使得剩余的数组是一个非减数组。由于子数组一定是连续的,则我们需要从中间删去某个长度的子数组使得数组剩余的两边拼接在一起后满足题目条件,那么前后的两个子数组自身必须要满足非减条件,因此可以先找到以数组开头作为起始和以数组末尾作为末尾的两个最长的符合条件的子数组。
找到该符合条件的子数组后,需要让两个子数组拼接后满足题目条件,则需要找到前面子数组中以某个数字结尾的部分和后面子数组中以某个数字开头的部分拼接后可以得到完整的满足条件的数组,则这个结尾的数字需不大于后面的开头的数字。同时使得从这两个数组中被丢弃的部分的长度和最小。
在得到前后两个最长数组后,若...