Лидеры в массиве

Сегодня мы рассмотрим задачу «Лидеры в массиве».

Элемент является лидером, если он больше всех элементов справа от него.

Мы можем решить эту задачу с помощью

1. два метода for-loop (простой)
2. метод for-loop (эффективный)

int[] findLeader(int[] arr) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < arr.length; i++) {
      boolean isLeader = true;
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] < arr[j]) {
          isLeader = false;
          break;
        }
      }
      if (isLeader) {
        result.add(arr[i]);
      }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
  }

В этом методе мы собираемся обойти массив, используя цикл i.
, проверяем, есть ли элемент больше, чем элемент, присутствующий в индексе i, используя другой цикл for j

если мы найдем элемент больше этого, мы не будем добавлять его в список, если нет, мы добавим этот элемент в результат.

Временная сложность: O(n²)

int[] findLeaderEfficient(int[] arr) {
    List<Integer> result = new ArrayList<>();
    int currentHigh = arr[arr.length - 1];
    result.add(currentHigh);
    for (int i = arr.length - 1; i > 0; i--) {
      if (arr[i] > currentHigh) {
        result.add(arr[i]);
        currentHigh=arr[i];
      }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
  }

В результат попадет элемент, находящийся последним в массиве, так как справа от него у нас нет ни одного элемента

мы объявляем currentHigh значением последнего элемента
двигаемся справа налево
проверяем, больше ли текущее число, чем currentHigh.
если да, то добавляем его в список результатов и устанавливаем этот элемент как currentHigh, если нет, то переходим к следующему элементу.

Временная сложность: O(n)