Минимизируйте длину массива, многократно удаляя элементы, которые меньше, чем следующий элемент
Учитывая массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы многократно удалять элементы, которые меньше, чем следующий элемент.
Примеры:
Input: arr[] = {20, 10, 25, 30, 40}
Output: 40
Explanation:
Below are the operations that are performed:
- Current array: arr[] = {20, 10, 25, 30, 40}
Currently, arr[1](= 10) is less than arr[2](= 25). Therefore, removing arr[1] modifies the array to {20, 25, 30, 40}.- Currently arr[0](= 20) is less than arr[1](= 25). Therefore, removing arr[0] modifies the array to {25, 30, 40}.
- Currently, arr[0](= 25) is less than arr[1](= 30). Therefore, removing arr[0] modifies the array to {30, 40}.
- Currently, arr[0](= 30) is less than arr[1](= 40). Therefore, removing arr[0] modifies the array to {40}.
Therefore, the remaining array is arr[] = {40}.
Input: arr[] = {2, 5, 1, 0}
Output: 5 1 0
Наивный подход. Самый простой подход к решению проблемы — пройтись по массиву и удалить элемент, если в диапазоне [i + 1, N — 1] есть элементы большего размера.
Временная сложность: O(N 2 )
Вспомогательное пространство: O(1)
Эффективный подход — итеративный. Описанный выше подход можно оптимизировать, просматривая массив с конца и отслеживая самый большой найденный элемент, и удаляя текущий элемент, если он меньше самого большого элемента. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте avector, скажем, res , чтобы сохранить результирующий массив.
- Инициализируйте переменную, скажем, maxi как INT_MIN, чтобы сохранить максимальное значение с конца.
- Обойдите массив arr[] в обратном порядке и выполните следующие шаги:
- Если значение arr[i] меньше maxi , продолжайте.
- В противном случае поместите элемент arr[i] в res и обновите значение maxi до максимума maxi и arr[i] .
- Обратить вектор res.
- После выполнения вышеуказанных шагов выведите вектор res в качестве результата.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)
Эффективный подход — рекурсивный . Вышеупомянутый подход также может быть реализован с использованием рекурсии. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте вектор, скажем, res , чтобы сохранить результирующий массив.
- Определите рекурсивную функцию, скажем, RecursiveDeleteFunction(int i) , чтобы удалить элемент, меньший, чем следующий элемент:
- Если значение i равно N , верните INT_MIN.
- Вызовите рекурсивно вызов функции RecursiveDeleteFunction(i+1) и сохраните возвращаемое значение в переменной, скажем, curr .
- Если значение arr[i] равно как минимум curr , то поместите arr[i] в векторное разрешение и обновите значение curr как максимальное из curr и arr[i] .
- Теперь верните curr .
- Вызовите функцию RecursiveDeleteFunction(0) , чтобы удалить меньшие элементы до следующих элементов, а затем инвертируйте вектор res .
- После выполнения вышеуказанных шагов выведите вектор res в качестве результата.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)