максимальное значение минимальных значений в подмассиве размера x

Я дал интервью одной компании, где они задали мне проблему минимального значения скользящего окна, как показано ниже:

 Find maximum value of minimum values in sub-array of size x
 e.g. arr = [2,5,4,6,8] and x = 3 then subarray would be [2,5,4], [5,4,6] and [4,6,8]. 
 The respective minimum values are 2,4 and 4. The maximum of these values is 4.

У меня есть код возврата ниже, но он дает Time Limit Exceeded для некоторого теста

public static int max(int x, List<Integer> num){
 int n = num.size();
 List<Integer> minList = new ArrayList<>();
 for(int i = 0; i <= n - x; i++){
    int minVal = Integer.MAX_VALUE;
    for(int j = i; j < i + x; j++){
        minVal = Math.min(min, num.get(j));
    }
    minList.add(minVal);
  }
  return Collections.max(minList);
}

Может кто поправит или укажет на правильный.


java algorithm sliding-window
person ppb    schedule 15.03.2021    source источник

Ответы (1)


arrow_upward
-1
arrow_downward

Временная сложность вашего кода равна O(n*m), но есть решение с временной сложностью O(n), для этого требуется всего один проход по массиву. Например, посмотрите здесь.

person Alex    schedule 15.03.2021
comment
Сказать, что есть решение, не намекая на то, что это за решение, не является полезным ответом. Может быть, это хороший комментарий, но это не ответ. - person Andreas; 15.03.2021
comment
Ответы, содержащие только ссылки, не являются хорошими ответами. - person Andreas; 15.03.2021