Holy HackerRank, Бэтмен! Недавно я выполнил испытание кода HackerRank под названием Загадка Мин-Макс. Это требует использования типа / структуры данных, называемого стеком, и на этом загадка не заканчивается. Перед написанием рабочего решения мне пришлось обратиться к множеству ресурсов, и я решил написать статью об этой проблеме, потому что хотел полностью ее понять и предложить ресурс JavaScript по алгоритму во всемирной паутине.
Прежде чем мы займемся проблемой кода, давайте рассмотрим, что такое стек. В информатике стек - это абстрактный тип данных, который служит коллекцией элементов, из которых сложение и вычитание могут выполняться только на задней стороне коллекции или, говоря вертикально, сверху стека. Хотя некоторые языки программирования предоставляют больше возможностей, при работе со стеком выполняются две основные операции:
- Push: добавить элемент в верхнюю часть стопки.
- Pop: удалить элемент из верхней части стопки.
Из-за того, что элементы добавляются или удаляются только с конца коллекции - или с вершины стека, другой терминологией для представления структуры данных стека является LIFO (последний пришел, первый ушел). Вот визуальное представление перехода к стеку и выхода из него:
Стек обычно представлен Array, который имеет методы .push() и .pop() в JavaScript и многих других языках программирования. Пример использования Array в качестве стека в JavaScript может выглядеть так:
const stack = [1, 2, 3] stack.push(4) // [1, 2, 3, 4] stack.push(5) // [1, 2, 3, 4, 5] stack.pop() // [1, 2, 3, 4] stack.pop() // [1, 2, 3]
Загадка Мин Макс:
Постановка задачи:
Учитывая Array положительных целых чисел, используйте серию скользящих окон для сбора минимального значения каждого окна, а затем запишите максимальное значение собранных минимумов для этого размера окна. Размер окна варьируется от 1 до n, где n равно размеру, т.е. длине ввода Array. Например:
const arr = [3, 5, 4, 7, 6, 2] // consider window sizes 1 to n = arr.length = 6 // wSize1 => [3] [5] [4] [7] [6] [2] // wSize2 => [3, 5] [5, 4] [4, 7] [7, 6] [6, 2] // ... // wSize6 => [3, 5, 4, 7, 6, 2] ____________________________________________________________________ | window | * collected minima * | window | * | | size | w1 | w2 | w3 | w4 | w5 | w6 | maximum | * | |––––––––––|–––––––––––––––––––––––––––––––––––––––––|–––––––––|–––| | 1 | 3 | 5 | 4 | 7 | 6 | 2 | 7 | c | |––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| o | | 2 | 3 | 4 | 4 | 6 | 2 | | 6 | l | |––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| l | | 3 | 3 | 4 | 4 | 2 | | | 4 | . | |––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| m | | 4 | 3 | 4 | 2 | | | | 4 | a | |––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| x | | 5 | 3 | 2 | | | | | 3 | i | |––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| m | | 6 | 2 | | | | | | 2 | a | –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– // maxima of minima = [7, 6, 4, 4, 3, 2]
Описание функции:
Функция riddle() должна возвращать Array целых чисел, представляющих максимальное минимальное значение для каждого окна размером от 1 до n.
Входной параметр:
arr:Arrayцелых чисел
Решение:
Алгоритм решения этой задачи требует много усилий, но не волнуйтесь, я запутался не меньше вас. Суть такова:
- Используйте
for loop,while loopи стекArrayдля построения хэш-карты максимумов окон. - Используйте
for loop, чтобы построить хэш-карту перевернутых максимумов окна. - Используйте оператор
for loop,if elseи хэш-карту перевернутых максимумов окна для сбора максимумов окон вArray. - Верните перевернутую копию максимума
Array.
Шаг 0: функция структуры
function riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = []
const result
return result
}
Начнем с описания функции riddle() с включенным параметром arr. Из схемы мы знаем, что нам понадобятся две Object для использования в качестве хэш-карты: wMaxes для первой хэш-карты максимума окна и wInver для второй хэш-карты инвертированных максимумов окна. Мы знаем, что нам нужны два Array: stack для использования в качестве стека и maxima для хранения значений из хэш-карты максимума инвертированного окна. Мы знаем, что нам нужно создать перевернутую копию maxima Array значений, поэтому мы объявим зарезервированную переменную result и в конечном итоге будем использовать ее в качестве возвращаемого значения.
Шаг 1. Создайте карту хеширования Window Maxima
function riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = []
arr.push(0)
for (let i = 0; i < arr.length; i++) {
let idx = i
while (stack.length && stack[stack.length - 1][0] >= arr[i]) {
let [val, prevIdx] = stack.pop()
wMaxes[arr[i]] = Math.max(
wMaxes[arr[i]] || 0, i - prevIdx + 1
)
wMaxes[val] = Math.max(wMaxes[val] || 0, i - prevIdx)
idx = prevIdx
}
stack.push([arr[i], idx])
}
delete wMaxes['0']
const result
return result
}
Первое, на что следует обратить внимание, - это первая строка активного кода: arr.push(0). Добавляя 0 в конец входного массива, мы можем эффективно создать дополнительную итерацию for loop и заставить while loop оценить любое оставшееся содержимое стека. Мы еще вернемся к этому.
for loop оценивает каждый элемент arr. Переменной idx присваивается индекс текущего элемента. Если stack пусто, как это будет на первой итерации, или значение в верхней части stack меньше, чем текущий элемент, while loop пропускается и вложенный Array, содержащий текущий элемент и его индекс помещается в stack. Обратите внимание, что idx является изменяемым.
Если stack не пусто и значение в верхней части stack больше или равно текущему элементу, запускается while loop, и здесь построен wMaxes.
stack.pop() удаляет суб-Array из вершины stack. Деструктурирующее присвоение используется для присвоения элемента переменной val и индекса переменной prevIdx.
Затем выполняются две операции с использованием скобок для добавления записей в wMaxes. В первом случае запись выполняется с ключом, равным текущему элементу (wMaxes[arr[i]]), и значением, равным большему из: текущего значения wMaxes[arr[i]], если оно существует, или значения текущий индекс минус предыдущий индекс плюс один (i — prevIdx + 1). Во втором случае запись выполняется с ключом, равным последнему элементу на вершине stack или предыдущему квалифицирующему элементу (wMaxes[val]), и значением, равным большему из: текущего значения wMaxes[val], если оно существует, или значение текущего индекса за вычетом предыдущего индекса (i — prevIdx).
Обратите внимание, что Logical OR operator (||) в каждой функции Math.Max() устанавливает первый аргумент в 0, если запись с указанным ключом еще не существует в wMaxes. Это сокращенный способ создания записи по умолчанию со вторым аргументом, вычисленным индексом, в качестве значения, если ключ еще не существует в wMaxes.
Последней операцией в while loop является установка переменной idx в области for loop на индекс из предыдущего элемента, вышедшего из верхней части stack. Обратите внимание, что при вычислении wMaxes[arr[i]] учитывается i — prevIdx + 1, чтобы учесть разницу в итерациях, начинающихся с 0, и размера окна, начинающегося с 1.
Итак, что, черт возьми, здесь происходит? Короче говоря, мы создаем хэш-карту wMaxes, в которой пары ключ-значение хранятся в виде ‘arr element': ‘window size', где ‘arr element’ - это элемент из arr, который представляет максимальное значение из собранных минимумов ‘window size’. Рассмотрим этот пример:
const arr = [3, 5, 4, 7, 6, 2]
wMaxes => {'0': 7, '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1}
____________________________________________________________________
| window | * collected minima * | window | * |
| size | w1 | w2 | w3 | w4 | w5 | w6 | maximum | * |
|––––––––––|–––––––––––––––––––––––––––––––––––––––––|–––––––––|–––|
| 2 | 3 | 4 | 4 | 6 | 2 | | 6 | m |
|––––––––––|––––––|––––––|––––––|––––––|––––––|––––––|–––––––––| a |
| 5 | 3 | 2 | | | | | 3 | x |
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
Структура данных стека играет здесь ключевую роль в том, что в ней в линейном порядке хранятся данные, предшествующие текущим оцененным данным. В конце этой статьи будет изящный журнал процесса, чтобы продемонстрировать, как данные обрабатываются во всей функции, но рассмотрим этот журнал процесса из третьей итерации for loop, оценивающий arr[2] // 4:
const arr = [3, 5, 4, 7, 6, 2]
loop #3
current element: 4
stack: [[3, 0], [5, 1]]
while loop
element on top of stack(5) is >= current element(4)
stack.pop(): [5, 1]
load window maxes map
build or update key:value with curEl(4) as key
set value to max of existing key(set to 0)
or index - last index + 1: 2
wMaxes: {'4': 2}
build or update key:value with lastEl(5) as key
set value to max of existing key(set to 0)
or index - last index: 1
wMaxes: {'4': 2, '5': 1}
change curIdx from 2 to 1
push [4, 1] (curEl, curIdx) on top of stack
stack: [[ 3, 0 ], [ 4, 1 ]]
Это показывает нам, что, если каждый элемент в arr больше, чем последний, он добавляется в стек для будущих вычислений, и как только мы дойдем до элемента в arr, который меньше чем последний, мы можем начать оценивать некоторые результаты с данными, которые у нас есть на данный момент; расширение окна, так сказать, обратно к предыдущему элементу. Акт расширения окна назад также контролируется установкой idx в prevIdx из последнего под-Array в верхней части stack, присвоения этого индекса следующему под-Array, который будет помещен в стек, подготавливая следующую итерацию for loop.
В журнале процесса loop #3 мы можем оценить текущий элемент: 4 и добавить его к wMaxes с размером окна 2, поскольку до сих пор:
minimum of [3, 5] = 3
minimum of [5, 4] = 4
maximum of 3, 4 = 4
wMaxes['4'] = 2 // {'4': 2}
Затем мы можем вернуться к предыдущему элементу: 5 через stack и добавить его к wMaxes с размером окна 1, поскольку до сих пор:
minimum of [3] = 3
minimum of [5] = 5
minimum of [4] = 4
maximum of 3, 5, 4 = 5
wMaxes['5'] = 1 // {'5': 1}
0, который был добавлен к arr в верхней части функции riddle(), заставит while loop обработать любые оставшиеся под-Array в stack на последней итерации for loop и соответствующим образом отрегулировать максимальные размеры окон, записанные в хэш-карте wMaxes.
Последний процесс для этого шага необязателен, но я включил его, чтобы удалить посторонний код. После сборки wMaxes будет включать ключ ‘0’ из-за последней итерации for loop. Если оставить, этот ключ будет просто проигнорирован на следующих шагах, но мы можем очистить код, удалив пару значений ключа из wMaxes с помощью delete wMaxes[‘0’].
Шаг 2. Создание хэш-карты максимума перевернутого окна
function riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = []
arr.push(0)
for (let i = 0; i < arr.length; i++) {
let idx = i
while (stack.length && stack[stack.length - 1][0] >= arr[i]) {
let [val, prevIdx] = stack.pop()
wMaxes[arr[i]] = Math.max(
wMaxes[arr[i]] || 0, i - prevIdx + 1
)
wMaxes[val] = Math.max(wMaxes[val] || 0, i - prevIdx)
idx = prevIdx
}
stack.push([arr[i], idx])
}
delete wMaxes['0']
for (let k in wMaxes) {
wInver[wMaxes[k]] = Math.max(wInver[wMaxes[k]] || 0, k)
}
const result
return result
}
Чтобы упростить построение нашего будущего maxima Array, мы можем инвертировать пары ключ-значение wMaxes и назначить их wInver хэш-карте. Этот шаг также будет обрабатывать необходимые поправки к максимальным размерам окна. Учти это:
const arr = [3, 5, 4, 7, 6, 2]
wMaxes = {'2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1}
Из-за порядка операций, выполняемых при построении wMaxes, одному и тому же размеру окна можно присвоить несколько значений. Проиллюстрировано выше: ‘5’ и ‘7’ оба назначены как максимальные размеры окна 1. Максимум может быть только один, поэтому мы отдаем предпочтение большему из двух значений: ‘7’.
Проще говоря, for loop выполняет итерацию по ключам (k) wMaxes и использует нотацию скобок для добавления записей в wInver с ключом, равным значению wMaxes[k], и значением, равным большему из: текущего значения wInver[wMaxes[k]], если оно существует, или значение текущего ключа: k. Наш пример предоставит это преобразование:
const arr = [3, 5, 4, 7, 6, 2]
wMaxes = {'2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1}
wInver = {'1': 7, '2': 6, '4': 4, '5': 3, '6': 2}
Шаг 3. Создайте массив Maxima
function riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = []
arr.push(0)
for (let i = 0; i < arr.length; i++) {
let idx = i
while (stack.length && stack[stack.length - 1][0] >= arr[i]) {
let [val, prevIdx] = stack.pop()
wMaxes[arr[i]] = Math.max(
wMaxes[arr[i]] || 0, i - prevIdx + 1
)
wMaxes[val] = Math.max(wMaxes[val] || 0, i - prevIdx)
idx = prevIdx
}
stack.push([arr[i], idx])
}
delete wMaxes['0']
for (let k in wMaxes) {
wInver[wMaxes[k]] = Math.max(wInver[wMaxes[k]] || 0, k)
}
maxima.push(wInver[arr.length - 1])
for (let i = arr.length - 2; i > 0; i--) {
if (!wInver[i] || wInver[i] < maxima[maxima.length - 1]) {
maxima.push(maxima[maxima.length - 1])
} else {
maxima.push(wInver[i])
}
}
const result
return result
}
Этот шаг начинается с помещения значения в maxima Array: максимум окна, который соответствует наибольшему размеру окна, или n: размер / длина arr. Обозначение скобок используется для доступа к максимальному значению окна из wInver с ключом arr.length — 1, который учитывает дополнительный элемент 0, который ранее был добавлен к arr.
Затем for loop проходит arr в обратном направлении, используя индекс уменьшения на основе arr.length, который оценивает максимум для размеров окна от n до 1, ссылаясь на хэш-карту wInver. Поскольку мы предварительно загружаем в массив максимальных значений wInver[arr.length — 1], for loop начинается со счетчика, установленного на arr.length — 2.
Внутри for loop оператор if else оценивает каждое значение wInver, к которому получил доступ ключ текущего индекса (i). Если wInver не включает ключ или полученное значение меньше, чем последний элемент maxima, последний элемент maxima добавляется к maxima - повторяется. В противном случае (но, как правило, если полученное значение больше, чем последний элемент maxima), полученное значение добавляется, или * добавляется к maxima. Обратите внимание, что maxima используется в качестве стека, ссылаясь только на конец или вершину стека и толкая элементы только на вершину стека.
Этот шаг кажется немного загадочным, но его цель и преимущество в том, что он может правильно использовать значения, которые мы собрали в wInver, правильно упорядочивать максимумы окна, чтобы они коррелировали с размером окна, и легко выдавать правильные значения, когда встречаются повторяющиеся минимумы окна. Контрольные точки можно просмотреть в журнале процесса, но примите во внимание это преобразование и вспомните диаграмму из постановки задачи:
const arr = [3, 5, 4, 7, 6, 2]
wMaxes = {'2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1}
wInver = {'1': 7, '2': 6, '4': 4, '5': 3, '6': 2}
maxima = [2, 3, 4, 4, 6, 7]
Шаг 4. Обратный массив Maxima и возврат
// complete solution
function riddle(arr) {
const wMaxes = {}
const wInver = {}
const stack = []
const maxima = []
arr.push(0)
for (let i = 0; i < arr.length; i++) {
let idx = i
while (stack.length && stack[stack.length - 1][0] >= arr[i]) {
let [val, prevIdx] = stack.pop()
wMaxes[arr[i]] = Math.max(
wMaxes[arr[i]] || 0, i - prevIdx + 1
)
wMaxes[val] = Math.max(wMaxes[val] || 0, i - prevIdx)
idx = prevIdx
}
stack.push([arr[i], idx])
}
delete wMaxes['0']
for (let k in wMaxes) {
wInver[wMaxes[k]] = Math.max(wInver[wMaxes[k]] || 0, k)
}
maxima.push(wInver[arr.length - 1])
for (let i = arr.length - 2; i > 0; i--) {
if (!wInver[i] || wInver[i] < maxima[maxima.length - 1]) {
maxima.push(maxima[maxima.length - 1])
} else {
maxima.push(wInver[i])
}
}
const result = maxima.reverse()
return result
}
И последнее, что нужно решить, - это порядок maxima Array. Хотя вся наша работа до сих пор требовала определенного порядка, результирующий maxima Array находится в порядке, обратном тому, который диктуется описанием функции. Напомним, что при построении maxima Array, arr проходился от конца (наибольший размер окна) до начала (наименьший размер окна). Однако в описании функции поясняется, что функция riddle() должна возвращать Array целых чисел, представляющих максимальное минимальное значение для каждого окна размером от 1 до n или от начала до конца.
Эту операцию легко выполнить многими способами, например for loop или удобными встроенными средствами, такими как .reverse(), которые тестовые примеры на HackerRank не возражали против использования. Чтобы правильно скомпилировать наш результат, мы присваиваем maxima.reverse() зарезервированной переменной, в нашем случае result, а затем возвращаем ее.
const arr = [3, 5, 4, 7, 6, 2] riddle(arr) // [7, 6, 4, 4, 3, 2]
Я не самый опытный программист или математик, но мне кажется, что даже Бэтмену будет сложно победить Загадочника с помощью такой головоломки, как Мин Макс Риддл! Как отмечалось ранее, я включил изящный журнал процесса функции riddle (), чтобы вы могли более глубоко проанализировать механизм кода. Возможно, есть лучшее решение этой проблемы, но теперь есть достойное, правильное, тщательно проанализированное JavaScript решение, на которое другие могут сослаться. Нанана 🦇!
Github.com/dangrammer
connected.com/in/danieljromans
danromans.com
Журнал процесса:
const arr = [3, 5, 4, 7, 6, 2]
riddle(arr)
// LOG /////////////////////////////////////////////////////////////
arr input
[ 3, 5, 4, 7, 6, 2 ]
add 0 to end of arr
[ 3, 5, 4, 7, 6, 2, 0 ]
______________________________________________________________
first for loop: build window maxes map
loop #1
current element, index: 3, 0
stack: []
stack empty
push [3, 0] on top of stack
stack: [ [ 3, 0 ] ]
loop #2
current element, index: 5, 1
stack: [ [ 3, 0 ] ]
element on top of stack(3) is < current element(5)
push [5, 1] on top of stack
stack: [ [ 3, 0 ], [ 5, 1 ] ]
loop #3
current element, index: 4, 2
stack: [ [ 3, 0 ], [ 5, 1 ] ]
while loop
element on top of stack (5) is >= current element: 4
stack.pop(): [ 5, 1 ]
load window maxes map
build or update key:value with curEl(4) as key
set value to max of [no key](0)
or [index - last index + 1](2)
wMaxes: { '4': 2 }
build or update key:value with prevEl(5) as key
set value to max of [no key](0)
or [index - last index](1)
wMaxes: { '4': 2, '5': 1 }
change curIdx from 2 to 1
push [4, 1] on top of stack
stack: [ [ 3, 0 ], [ 4, 1 ] ]
loop #4
current element, index: 7, 3
stack: [ [ 3, 0 ], [ 4, 1 ] ]
element on top of stack(4) is < current element(7)
push [7, 3] on top of stack
stack: [ [ 3, 0 ], [ 4, 1 ], [ 7, 3 ] ]
loop #5
current element, index: 6, 4
stack: [ [ 3, 0 ], [ 4, 1 ], [ 7, 3 ] ]
while loop
element on top of stack (7) is >= current element: 6
stack.pop(): [ 7, 3 ]
load window maxes map
build or update key:value with curEl(6) as key
set value to max of [no key](0)
or [index - last index + 1](2)
wMaxes: { '4': 2, '5': 1, '6': 2 }
build or update key:value with prevEl(7) as key
set value to max of [no key](0)
or [index - last index](1)
wMaxes: { '4': 2, '5': 1, '6': 2, '7': 1 }
change curIdx from 4 to 3
push [6, 3] on top of stack
stack: [ [ 3, 0 ], [ 4, 1 ], [ 6, 3 ] ]
loop #6
current element, index: 2, 5
stack: [ [ 3, 0 ], [ 4, 1 ], [ 6, 3 ] ]
while loop
element on top of stack (6) is >= current element: 2
stack.pop(): [ 6, 3 ]
load window maxes map
build or update key:value with curEl(2) as key
set value to max of [no key](0)
or [index - last index + 1](3)
wMaxes: { '2': 3, '4': 2, '5': 1, '6': 2, '7': 1 }
build or update key:value with prevEl(6) as key
set value to max of existing key(2)
or [index - last index](2)
wMaxes: { '2': 3, '4': 2, '5': 1, '6': 2, '7': 1 }
change curIdx from 5 to 3
while loop
element on top of stack (4) is >= current element: 2
stack.pop(): [ 4, 1 ]
load window maxes map
build or update key:value with curEl(2) as key
set value to max of existing key(3)
or [index - last index + 1](5)
wMaxes: { '2': 5, '4': 2, '5': 1, '6': 2, '7': 1 }
build or update key:value with prevEl(4) as key
set value to max of existing key(2)
or [index - last index](4)
wMaxes: { '2': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
change curIdx from 3 to 1
while loop
element on top of stack (3) is >= current element: 2
stack.pop(): [ 3, 0 ]
load window maxes map
build or update key:value with curEl(2) as key
set value to max of existing key(5)
or [index - last index + 1](6)
wMaxes: { '2': 6, '4': 4, '5': 1, '6': 2, '7': 1 }
build or update key:value with prevEl(3) as key
set value to max of [no key](0)
or [index - last index](5)
wMaxes: { '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
change curIdx from 1 to 0
push [2, 0] on top of stack
stack: [ [ 2, 0 ] ]
loop #7
current element, index: 0, 6
stack: [ [ 2, 0 ] ]
while loop
element on top of stack (2) is >= current element: 0
stack.pop(): [ 2, 0 ]
load window maxes map
build or update key:value with curEl(0) as key
set value to max of [no key](0)
or [index - last index + 1](7)
wMaxes: { '0': 7, '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
build or update key:value with prevEl(2) as key
set value to max of existing key(6)
or [index - last index](6)
wMaxes: { '0': 7, '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
change curIdx from 6 to 0
push [0, 0] on top of stack
stack: [ [ 0, 0 ] ]
______________________________________________________________
window maxes map (wMaxes)
{ '0': 7, '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
remove 0 key from wMaxes
{ '2': 6, '3': 5, '4': 4, '5': 1, '6': 2, '7': 1 }
______________________________________________________________
second for loop: create inverted window maxes map
loop #1
current key: 2
add key(wMaxes[2]) to wInver: 6
set value for wInver key(6) to the greater of:
[wInver[wMaxes[2]] || 0](0) & current key(2)
{ '6': 2 }
loop #2
current key: 3
add key(wMaxes[3]) to wInver: 5
set value for wInver key(5) to the greater of:
[wInver[wMaxes[3]] || 0](0) & current key(3)
{ '5': 3, '6': 2 }
loop #3
current key: 4
add key(wMaxes[4]) to wInver: 4
set value for wInver key(4) to the greater of:
[wInver[wMaxes[4]] || 0](0) & current key(4)
{ '4': 4, '5': 3, '6': 2 }
loop #4
current key: 5
add key(wMaxes[5]) to wInver: 1
set value for wInver key(1) to the greater of:
[wInver[wMaxes[5]] || 0](0) & current key(5)
{ '1': 5, '4': 4, '5': 3, '6': 2 }
loop #5
current key: 6
add key(wMaxes[6]) to wInver: 2
set value for wInver key(2) to the greater of:
[wInver[wMaxes[6]] || 0](0) & current key(6)
{ '1': 5, '2': 6, '4': 4, '5': 3, '6': 2 }
loop #6
current key: 7
add key(wMaxes[7]) to wInver: 1
set value for wInver key(1) to the greater of:
[wInver[wMaxes[7]] || 0](5) & current key(7)
{ '1': 7, '2': 6, '4': 4, '5': 3, '6': 2 }
______________________________________________________________
inverted window maxes map (wInver)
{ '1': 7, '2': 6, '4': 4, '5': 3, '6': 2 }
load maxima arr with value from wInver[6(last index of input arr)]
[ 2 ]
______________________________________________________________
third for loop: create maxima arr
loop #1
the value of wInver[5](3) is >= the last element of maxima(2)
so add new value
[ 2, 3 ]
loop #2
the value of wInver[4](4) is >= the last element of maxima(3)
so add new value
[ 2, 3, 4 ]
loop #3
wInver has no key of 3 so repeat last element
[ 2, 3, 4, 4 ]
loop #4
the value of wInver[2](6) is >= the last element of maxima(4)
so add new value
[ 2, 3, 4, 4, 6 ]
loop #5
the value of wInver[1](7) is >= the last element of maxima(6)
so add new value
[ 2, 3, 4, 4, 6, 7 ]
______________________________________________________________
reverse the maxima arr and assign it to result arr
print result arr
[ 7, 6, 4, 4, 3, 2 ]
