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

qiubit 发表于 Dev

qiubit

我正在尝试以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是对优先级队列的引用，该优先级队列首先返回最少的元素。仍然可以通过简单的方法在O（n）中完成此操作吗？

平面的

这是一个很好的小难题！这是基于双端队列的解决方案。

我的算法与您的算法基本相同，除了我使用出队记录来跟踪最小值：队列包含递增的值序列：第一个是当前间隔的最小值，第二个是当前间隔的最小值在第一个最小值之后开始的子间隔，依此类推。

当我将左指针移过最小值时，我从队列的左侧删除了该值，队列的其余部分自然以剩余间隔的最小值开始。

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

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

当心：我正在使用（并返回）半开放间隔，因为它们比封闭间隔更容易出错。

此代码仅经过轻微测试。为了表明它是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