求助|一些关于单调队列的问题想要请教大佬们

6 小时前

5 小时前

发布于江苏

这两周打了周赛，遇到单调队列总会遇到超时的情况，基本上打不了，只能眼睁睁看着掉分，这里以488场周赛为例，我使用的是C#，如果我采用和灵神题解一样的方法，就会超时，采用的是LinkedList作为双端队列使用，出现了这样的情况，几乎完全相同的算法，在C#上超时严重，而我采用自己编写双端队列，自己造轮子才能避免这一点，可是自己造轮子的时间太长，对于周赛来说是完全不利的，想问问各位大佬，有没有可以替代LinkedList，优化时间的双端队列可以使用，或者在周赛时直接复制自己准备好的双端队列，自己写过的轮子，在其之上进行修改是否合规。

无法通过测试的代码：

public class Solution {
    public long CountSubarrays(int[] nums, long k) {
        LinkedList<int> list_min = new LinkedList<int>();
        LinkedList<int> list_max = new LinkedList<int>();
        int n = nums.Length, left = 0, right = 0;
        long ans = 0;
        while(right < n){
            while(list_min.Count > 0 && nums[list_min.Last()] >= nums[right]){
                list_min.RemoveLast();
            }
            while(list_max.Count > 0 && nums[list_max.Last()] <= nums[right]){
                list_max.RemoveLast();
            }
            list_min.AddLast(right);
            list_max.AddLast(right);

            int min = nums[list_min.First()], max = nums[list_max.First()];
            while((long)(max - min) * (right - left + 1) > k){
                if(list_min.First() == left){
                    list_min.RemoveFirst();
                }
                if(list_max.First() == left){
                    list_max.RemoveFirst();
                }
                min = nums[list_min.First()];
                max = nums[list_max.First()];
                left++;
            }
            ans += right - left + 1;
            right++;
        }
        return ans;
    }
}

自己构造双端队列的代码：

public class Solution {
    public class DLinkedNode{
        public int val;
        public DLinkedNode prev;
        public DLinkedNode next;

        public DLinkedNode(int val = -1, DLinkedNode prev = null, DLinkedNode next = null){
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }

    public class DLinkedList{
        private DLinkedNode head;
        private DLinkedNode tail;

        public DLinkedList(){
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.prev = head;
        }

        public bool IsEmpty(){
            if(head.next == tail){
                return true;
            }
            return false;
        }

        public void AddLast(int val){
            DLinkedNode node = new DLinkedNode(val);
            node.prev = tail.prev;
            node.next = tail;
            tail.prev.next = node;
            tail.prev = node;
        }

        public int First(){
            return head.next.val;
        }

        public int Last(){
            return tail.prev.val;
        }

        public void RemoveFirst(){
            if(IsEmpty()){
                return;
            }
            RemoveNode(head.next);
        }

        public void RemoveLast(){
            if(IsEmpty()){
                return;
            }
            RemoveNode(tail.prev);
        }

        private void RemoveNode(DLinkedNode node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    public long CountSubarrays(int[] nums, long k) {
        DLinkedList list_min = new DLinkedList();
        DLinkedList list_max = new DLinkedList();
        int n = nums.Length, left = 0, right = 0;
        long ans = 0;
        while(right < n){
            while(!list_min.IsEmpty() && nums[list_min.Last()] >= nums[right]){
                list_min.RemoveLast();
            }
            while(!list_max.IsEmpty() && nums[list_max.Last()] <= nums[right]){
                list_max.RemoveLast();
            }
            list_min.AddLast(right);
            list_max.AddLast(right);

            int min = nums[list_min.First()], max = nums[list_max.First()];
            while((long)(max - min) * (right - left + 1) > k){
                if(list_min.First() == left){
                    list_min.RemoveFirst();
                }
                if(list_max.First() == left){
                    list_max.RemoveFirst();
                }
                min = nums[list_min.First()];
                max = nums[list_max.First()];
                left++;
            }
            ans += right - left + 1;
            right++;
        }
        return ans;
    }
}