分割数组
题目
给定一个数组 nums ,将其划分为两个连续子数组 left 和 right, 使得:
left 中的每个元素都小于或等于 right 中的每个元素。left 和 right 都是非空的。left 的长度要尽可能小。在完成这样的分组后返回 left 的 长度 。
用例可以保证存在这样的划分方法。
复制代码
题解
拿到题首先想到是朴素的做法,就是每个点依次向左右扩展,如果发现左边的最大值一直小于右边的最小值,那么该点就是答案。但是该方法时间复杂度是 O(n* n),看一下数据量应该不能过。
那就想到通过离散化排序,我们把数组的下标保存,然后排序,从左往右再遍历下如果排序的最大值和下标相同,说明从左往右能组成连续的且排序小于右半部分的数组。该方法的时间复杂度是 O(n*logn);
双指针的办法也是一开始就想到的,优先缩减右半部分,但是发现会缩过头。后来也是加上数组保存前缀最大值和后缀最小值,然后往后去修正。看了题解才感觉有点 low,哈哈哈。
复制代码
版权声明: 本文为 InfoQ 作者【掘金安东尼】的原创文章。
原文链接:【http://xie.infoq.cn/article/e206a69df5bf9e5bc0eca011b】。文章转载请联系作者。
评论