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

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

Вот ссылка на проблему на leetcode, где я использовал это:

Https://leetcode.com/problems/maximum-width-ramp/

Подход 1

Не совсем «найти» по каждому индексу, лучше подумать. Проблема состоит в том, чтобы найти максимум из всех таких расстояний, поэтому хитрость в том, что для многих индексов мы можем исключить это вычисление.

Для 6 0 8 2 1 5, когда я знаю, что для 0 правый конец рампы (назовем его idx2) равен 5, мне не нужно рассчитывать его для чисел, находящихся между 0 и 5 для случай idx2 = 5, так как их расстояние до 5 в любом случае будет меньше, чем расстояние от 0 до 5.

Классическая задача двух указателей. Правый указатель расширяет диапазон, а левый указатель сжимает его. Уловка заключается в том, что левый указатель выполняет итерацию по исходному массиву, а правый указатель выполняет итерацию по массиву, в котором хранится максимальное количество. справа для каждого индекса.

O(n)

Код:

public int maxWidthRampI(int[] A) {
  int n = A.length;
  int[] rMax = new int[n];
  rMax[n - 1] = A[n - 1];
  for (int i = n - 2; i >= 0; i--) {
    rMax[i] = Math.max(rMax[i + 1], A[i]);
  }
  int left = 0, right = 0;
  int ans = 0;
  while (right < n) {
    while (left < right && A[left] > rMax[right]) {
      left++;
    }
    ans = Math.max(ans, right - left);
    right++;
  }
  return ans;
}

Этот подход работает быстрее всего на leetcode.

Подход 2

Сортировка индексов в отдельном массиве по элементам.

Для 7 2 5 4 массив индексов будет [1, 3, 2, 0]. Теперь эти индексы расположены в порядке неубывания элементов. Таким образом, для любого i ‹j, если index [i]‹ index [j] (т.е. меньший элемент появляется перед большим элементом в исходном массиве), он квалифицируется как кандидат на решение. Итак, повторяйте и поддерживайте минимальный индекс, встреченный до сих пор.

O (nlogn)

Код:

public int maxWidthRampII(int[] A) {
  int n = A.length;
  Integer[] b = new Integer[n];
  for (int i = 0; i < n; i++) {
    b[i] = i;
  }
  Arrays.sort(b, Comparator.comparingInt(i -> A[i]));
  int mn = n;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans = Math.max(ans, b[i] - mn);
    mn = Math.min(mn, b[i]);
  }
  return ans;
}

Подход 3

На основе стека.

Держите стопку элементов убывающего порядка.

Возьмем пример: [6,0,8,2,1,5]

Уменьшение стопки заказов: 6,0.

Нет смысла добавлять 8 в стек.

Так как для любого элемента справа, для которого 8 будет частью решения (т. Е. 8 находится на левом конце рампы), 0 также может быть левым концом для этой рампы и обеспечивает большую длину рампы, поскольку индекс 0 равен меньше, чем у 8. Это гарантирует, что восьмёрка никогда не будет левым концом нашей самой большой рампы.

Аналогичное объяснение применимо к 2,1 и 5.

Теперь, когда у нас есть стек, начните перебирать массив с конца, учитывая:

Текущий элемент должен быть правым концом пандуса, а верхний элемент стека - левым концом пандуса. Если верхний элемент стека удовлетворяет условию, у нас есть кандидатная рампа.

Уловка здесь заключается в следующем: теперь мы можем извлечь этот элемент из стека. Почему?

Допустим, сейчас мы находимся в индексе j массива, а вершина стека находится в индексе i.

Так что рампа - это я ...

Поскольку мы выполняем итерацию в обратном направлении в массиве, следующим возможным правым концом рампы будет j-1. Даже если образует пандус с i, его длина будет короче, чем у нынешнего пандуса (т. Е. J-i).

Итак, сейчас нет смысла хранить 0 в стеке.

Продолжайте извлекать элементы из стека всякий раз, когда у нас есть кандидатная рампа. Поскольку текущий кандидатный наклон - лучший вариант, учитывая, что верхний элемент стека находится у левого конца этого пика.

Код:

public int maxWidthRampIII(int[] A) {
  int n = A.length;
  Stack<Integer> st = new Stack<>();
  for (int i = 0; i < n; i++) {
    if (st.empty() || A[i] < A[st.peek()]) {
      st.push(i);
    }
  }
  int ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    while (!st.empty() && A[i] > A[st.peek()]) {
      ans = Math.max(i - st.pop(), ans);
    }
  }
  return ans;
}

Не стесняйтесь комментировать / писать мне в случае каких-либо сомнений.