Баруун талын Leetcode шийдэл дээрх элементүүдийг хамгийн сайн элементээр солино уу


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны
Array

Баруун талын 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 шийдлийн элементүүдийг хамгийн сайн элементээр солих код

C ++ код

#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), алгоритм нь газар дээр нь байрладаг тул орон зайн нарийн төвөгтэй байдал тогтмол байдаг.