每个大小为k的窗口中的第一个负整数,辅助空间为O(1)

我试着理解你的逻辑,但我不太明白。以下是我从零开始的想法:

class demo2 {

    public static void maximum (int arr[], int k){
        for (int j = 0; j < arr.length - k + 1; j++) {
            boolean found = false;
            for (int x = j; x < j + k; x++) {
                if (arr[x] < 0) {
                    System.out.println(arr[x]);
                    found = true;
                    break;
                }
            }
            if (!found)
                System.out.println(0);
        }
    }

    public static void main(String[] args) {
        int arr[] = { -2, 5, 1, 8, -2, 9, -1 };
        int k = 2;
        maximum(arr, k);
    }
}

结果:

-2
0
0
-2
-2
-1

我认识到,如果阵列长度和窗口大小都非常大,可能有一种更有效的方法来实现这一点,这将非常重要。但你的问题并没有说明情况如此。这是一个地方,你需要确保你想花时间优化,超越简单和明显的解决方案。

它可以用真正的线性复杂度来实现 O(n) (与使用 多项式的 复杂性 O(n*k) ):

public static void maximum (int arr[], int k) {
    int index = -1;
    for (int i = arr.length - 1; i >= 0; i--) {
        if (index >= i + k) {
            index = -1;
        }
        if (arr[i] < 0) {
            index = i;
        }
        arr[i] = index >= 0 ? arr[index] : 0;
    }
    for(int i = 0; i <= arr.length - k; i++) {
        System.out.println(arr[i]);
    }
}

更新: 甚至更好,不用写信给 arr 数组:

public static void maximum (int arr[], int k) {
    int index = -1;
    for (int i = 0; i < arr.length - k + 1; i++) {
        if(index < i) {
            // Find the index of the next negative number
            do {
                index++;
            } while (index < arr.length && arr[index] >= 0);
        }
        // If the next negative number is within the window print it,
        // otherwise print "0"
        System.out.println(index < i + k ? arr[index] : 0);
    }
}

就(内部)循环的迭代次数而言,与朴素算法O(n*k)进行比较(最坏情况下,即当表中根本没有负数时):

            | naive        | dynamic |
            | O((n-m+1)*m) | O(n)    |
--------------------------------------
  n=7,  m=2 |           12 |       7 |
 n=10,  m=2 |           18 |      10 |
n=100, m=10 |          910 |     100 |
n=100, m=50 |         2550 |     100 |     

我有一个C++解决方案,我也已经提交了这个代码在GFGS实践问题,并得到了认可。时间复杂度为O(n),辅助空间复杂度为O(K)

vector<int> firstNegative(vector<int> arr, int lenn, int k)
{
  vector <int> ans;
  int start = 0, end = 0;
  queue <int> index;
  while(start <= lenn-k)
  {
    if(arr[end] < 0)
      index.push(end);

      
    if(k == (end-start+1))
    {
      if(index.empty())
        ans.push_back(0);
      else
      {
        if(index.front()>=start && index.front()<=end)
          ans.push_back(arr[index.front()]);
        else
        {
          index.pop();
          continue;
        }
      }
      start++;
    }
    end++;
  }
  return ans;
}

     Deque<Long> queue = new LinkedList<>();
     int C=N-K+1;
        long[] output = new long[C];
        int c = -1;
        int startWindow = 0;
        int endWindow =K;
        boolean firstFlag=true;
        while (true) {
            for(int j=startWindow;j<endWindow;j++){
                if(A[j] < 0 && firstFlag){
                  //  queue.add(A[j]);
                  if(c<C-1){
                    output[++c]=A[j];
                  }
                    firstFlag=false;
                    break;
                }
                if(j>=N-1) {
                    break;
                }
            }
            if(firstFlag){
                if(c<C-1){
                    output[++c]=0;
                  }
              //  queue.add((long)0);
            }
            if(endWindow>=N){
                break;
            }
            firstFlag=true;
            startWindow=startWindow+K-1;
            endWindow=startWindow+K;
        }
//      while(!queue.isEmpty())
//            output[++c] = queue.remove();
        return output;

function one_loop() {

    $arr = [-12, -1, 7, -8, 15, 30, -16, -30, 40, 3];
    $arr_len = count($arr); // 7
    $result = [];
    $k = 2;
    $i = 0;
    $j = 0;

    while ($j < $arr_len && $i < $arr_len-$k+1) {       
        $flag = false;
        $window_size = $j-$i+1;
        if($arr[$j] < 0) {
            array_push($result, $arr[$j]);
            $flag = true;
        }
        if($window_size == $k && $flag == false){
            array_push($result, 0);
            $i++;
            $j = $i;
        } elseif ($flag == true) {
            $i++;
            $j = $i;
        } elseif ($flag == false && $window_size != $k) {
            $j++;
        }
    }
    echo implode($result, ", ");
}