Замініть елементи на найбільший елемент на правому боці рішення Leetcode


Рівень складності Легко
Часто запитують у Амазонка
масив

Проблема Заміна елементів на Найбільший елемент на правому боці Рішення Leetcode надає нам масив або вектор цілих чисел. Проблема попросила нас замінити всі елементи елементом, який є найбільшим серед усіх елементів праворуч. Тож розглянемо, чи мав ми масив чи послідовність, {a, b, c}. Якщо цифри відповідають тенденції, b> c> a. Отже, відповідно до запитання, результат повинен бути {b, c, -1}. Перш ніж зануритися в глибину розв’язання, давайте перевіримо кілька прикладів.

Замініть елементи на найбільший елемент на правому боці рішення Leetcode

[17,18,5,4,6,1]
[18,6,6,6,1,-1]

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

[400]
[-1]

Пояснення: Оскільки праворуч від поточного числа немає елемента. Таким чином ми повертаємо -1 як вихід.

Підхід до заміни елементів найкращим елементом на правому боці рішення Leetcode

Проблема чітко формулює проблему самою назвою. Проблема говорить про заміну кожного елемента найбільшим елементом, який зустрічається з правого боку від нього. Тепер залишається лише імітувати процес. Ми можемо легко це зробити, якщо розпочати обхід масиву з правого боку. Отже, замість того, щоб йти з лівого боку, ми починаємо з правого боку. Ми зберігаємо елемент, що зберігає максимально знайдений елемент до цього часу. Ми зберігаємо поточний елемент у змінній, а потім продовжуємо оновлювати максимальне значення. На даний момент ми можемо замінити поточний елемент на найбільший елемент / максимальний елемент.

Код для заміни елементів найбільшим елементом на правому боці рішення Leetcode

Код С ++

#include <bits/stdc++.h>
using namespace std;

vector<int> replaceElements(vector<int>& arr) {
    int mx = -1, a;
    int n = arr.size();
    for (int i = n - 1; i >= 0; --i) {
        a = arr[i];
        arr[i] = mx;
        mx = max(mx, a);
    }
    return arr;
}

int main(){
    vector<int> arr = {17,18,5,4,6,1};
    vector<int> output = replaceElements(arr);
    for(int i=0;i<6;i++)
        cout<<output[i]<<" ";
}
18 6 6 6 1 -1

Код Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
  public static int[] replaceElements(int[] arr) {
        int mx = -1, a;
        int n = arr.length;
        for (int i = n - 1; i >= 0; --i) {
            a = arr[i];
            arr[i] = mx;
            mx = Math.max(mx, a);
        }
        return arr;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {17,18,5,4,6,1};
    int[] output = replaceElements(arr);
    for(int i=0;i<6;i++)
      System.out.print(output[i]+" ");
  }
}
18 6 6 6 1 -1

Аналіз складності

Часова складність

O (N), оскільки ми переходимо масив один раз. Складність часу також лінійна.

Складність простору

O (1), алгоритм є місцем, і, отже, складність простору постійна.