В этом посте я представлю три подхода к решению проблемы структур данных, которые могут оказаться полезными в нескольких сценариях.
По сути, нам нужно решить эту проблему: учитывая массив, для каждого индекса нам нужно найти самый дальний больший элемент справа.
Вот ссылка на проблему на 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; }
Не стесняйтесь комментировать / писать мне в случае каких-либо сомнений.