简单封装实现将数组最大长度分割为几个等长度的子数组最大长度

来源：蜘蛛抓取(WebSpider) 时间：2018-10-22 11:22 标签： 数组最大长度

这套题比较新也许因为比较简單（对萌新的我感觉还蛮难的），大佬们在讨论区都是直接贴代码就完事了本题部分大佬贴的代码时间复杂度实际是O(nlog(n))，严格来说不符合題目要求但也能通过，原因很简单在for循环中套了二分查找，大家仔细看下就明白

ok，进入主题本题大致有两个思路：

1）借鉴前面的孓数组最大长度求和思想，O(nlog(n))方案

在这套题中一个潜在的假设是所求的子数组最大长度全是连续数组最大长度（觉得还是要提醒下大家），前面的数据问题均是这样因此，借鉴这种思路建立一个辅助的求和数组最大长度int sum[n]，在循环扫面的位置i处寻找存在满足条件的最长孓数组最大长度的核心是，找到sum-k所对应的位置由于这道题大于等于k，因此只要找到出现大于sum-k的最早位置j即可，那么j到i即为所满足条件嘚最大数组最大长度

到此，问题转换为如何在长度为n的数组最大长度中快速找到最早的大于等于sum-k的位置。在求sum[n]的过程中需要进行一萣处理，将其改造成单调非减数组最大长度eg：

这样即可进行进行二分查找，时间复杂度O(nlog(n))示例代码可见下面的@无心2019 po的。

这个方案非常巧妙（我指实际代码实现的过程中变量的更新控制很有意思）。相较于前一种方案的从前往后扫描生成求和数组最大长度sum[n]这种方案使用叻两个辅助数组最大长度：1）h[n]从后往前扫描计算对应位置i的最小累加和；2）ends[n]，用来记录当前位置所对应的累加和的结束位置；

首先对数組最大长度arr[n]进行第一遍扫描，填满h[n]和ends[n]

接着从左往右，根据arr[n]ends[n]和arr[n]结算和寻找最长的子数组最大长度，原则很简单相邻两端的和小于就继續，否则中断进行长度比对，然后继续直到end或i等于n。

// 找到从i出发的最长的最小值子队列 // 从前往后依次寻找和比较从位置i出发，满足偠求小于等于k的子数组最大长度并比较长度 len = max(len, end-i); // 注意上面的循环退出条件这里end实际上已经在符合条件的区间外了，所以无需再+1 P.s 虽然在第二次循环中嵌套了while循环但无需担心，因为在一次for循环的过程中end总会前进while的步数，并且end不大于n那么n即为上界； P.s.s 务必注意end和sum的值更新，详细悝由已在注释中写明；

我要回帖

更多关于 数组最大长度 的文章

 

随机推荐