讨论/题目交流/🏆 第 187 场力扣周赛/
🏆 第 187 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 旅行终点站
4 分 - 是否所有 1 都至少相隔 k 个元素
5 分 - 绝对差不超过限制的最长连续子数组
7 分 - 有序矩阵中的第 k 个最小数组和

展开讨论

第 3 题反复报超时,明明O(n)的算法,最后 2 分钟才发现linq的last()是个O(n)的函数...所以复杂度是O(n^2)

链表的linq Last()扩展函数是O(n) 修改为 链表自带属性 Last O(1)

        public int LongestSubarray(int[] nums, int limit)
        {
            var res = 0;
            var l = -1;
            var big = new LinkedList<int>();
            var small = new LinkedList<int>();
            for (var r = 0; r < nums.Length; r++)
            {
                if (l == -1)
                {
                    l = r;
                    big.AddLast(r);
                    small.AddLast(r);
                }
                else
                {
                    while (big.Any() && nums[r] > nums[big.Last.Value])
                        big.RemoveLast();
                    big.AddLast(r);

                    while (small.Any() && nums[r] < nums[small.Last.Value])
                        small.RemoveLast();
                    small.AddLast(r);

                    while (nums[big.First.Value] - nums[small.First.Value] > limit)
                    {
                        if (big.First() == l)
                            big.RemoveFirst();
                        if (small.First() == l)
                            small.RemoveFirst();
                        l++;

                        if (!big.Any() || !small.Any())
                            break;
                    }
                }

                res = Math.Max(res, r - l + 1);
            }

            return res;
        }
展开全部 18 讨论