查找数组中的最大段，使其中的最小值大于或等于段的大小

Question

我正在尝试以 O(n) 复杂度完成以下任务：

Given an array [|x_1,x_2,...,x_n|] return the biggest s such that there exists 
a segment of length s - [|x_i,x_(i+1),...,x_j|], in which the minimum value 
is greater or equal (j-i+1).

更新：这里有一个不正确的 O(n) 解决方案，我设法编写了正确的（至少我是这么认为的）简单的 O(n*log n) 解决方案。这是：

let segment a = 
    let n = Array.length a in
    let pointer_1 = ref 0 in
    let pointer_2 = ref 0 in
    let q = ref (put empty_queue (a.(0), 0)) in
    let best = ref 0 in
    begin
        while (!pointer_2 < n) do
            let size = (!pointer_2 - !pointer_1 + 1) in
            q := put !q (a.(!pointer_2), !pointer_2);
            let ((lmin, pmin), qright) = getmin !q in
            if (size > lmin) then begin
                best := max !best (size-1);
                pointer_1 := pmin + 1;
                pointer_2 := !pointer_2 + 1;
                q := qright
            end
            else
                begin
                    best := max !best (size);
                    pointer_2 := !pointer_2 + 1
                end
        done;
        !best
    end;;

其中 q 是对优先级队列的引用，其中 returns 最少元素优先。不过，这能否以简单的方式在 O(n) 中完成？

Answer 1

这是一个不错的小拼图！这是基于双端队列的解决方案。

我的算法与你的大部分相同，只是我使用出列来跟踪最小值：队列包含递增的值序列：第一个是当前间隔的最小值，第二个一个是第一个最小值之后开始的子区间的最小值，依此类推。

当我将左指针前进到超过最小值时，我从队列的左边删除这个值，队列的其余部分自然从剩余间隔的最小值开始。

当我向右指针前进时，我检查队列右侧的新值。如果新值较小，我会删除最右边的条目并再次检查剩余的队列。当删除所有更大的值时，我可以在出列的末尾添加新值。

当在数组中发现非正值时，我不得不添加一个特殊情况：同时推进两个指针。

注意：我正在使用（并返回）半开区间，因为它们比闭区间更不容易出错。

此代码仅经过轻微测试。为了证明它是 O(n)，请注意每个值在出队中最多输入一次。

let segment a =
  let len = Array.length a in
  let p1 = ref 0 in
  let p2 = ref 0 in
  let bestlen = ref 0 in
  let best = ref [(0,0)] in
  let q = Dq.make len in
  while !p2 < len do
    let l = !p2 - !p1 in
    if (Dq.is_empty q || Dq.peek_left q > l) && a.(!p2) > l
    then begin
      while not (Dq.is_empty q) && Dq.peek_right q > a.(!p2) do
        Dq.pop_right q;
      done;
      Dq.push_right q a.(!p2);
      incr p2;
    end else if !p1 < !p2 then begin
      if a.(!p1) = Dq.peek_left q then Dq.pop_left q;
      incr p1;
    end else begin
      assert (Dq.is_empty q);
      incr p1;
      incr p2;
    end;
    let l = !p2 - !p1 in
    if l > !bestlen then begin
      bestlen := l;
      best := [];
    end;
    if l = !bestlen then best := (!p1, !p2) :: !best;
  done;
  !best
;;

这是双端队列的基本实现，具体针对上述代码：

module Dq = struct
  type t = {
    mutable hd : int;
    data : int array;
    mutable tl : int;
  }
  let make len = {
    hd = 0;
    data = Array.make len 0;
    tl = 0;
  };;
  let push_right q x =
    assert (q.tl < Array.length q.data);
    q.data.(q.tl) <- x;
    q.tl <- q.tl + 1;
  ;;
  let is_empty q = q.tl = q.hd;;
  let peek_right q =
    assert (q.hd < q.tl);
    q.data.(q.tl - 1)
  ;;
  let peek_left q =
    assert (q.hd < q.tl);
    q.data.(q.hd)
  ;;
  let pop_left q =
    assert (q.hd < q.tl);
    q.hd <- q.hd + 1;
  ;;
  let pop_right q =
    assert (q.hd < q.tl);
    q.tl <- q.tl - 1;
  ;;
end

查找数组中的最大段，使其中的最小值大于或等于段的大小

Finding the biggest segment in array such that minimum value in it is greater or equal the segment's size

algorithm

ocaml