Artan Elementlər Arasındakı Maksimum Fərq LeetCode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Cisco ExpediaBaxılıb 33

Problem bəyanat

Artan elementlər arasındakı maksimum fərq LeetCode Həlli – a 0 indeksli tam sıra nums ölçüdə n, tapmaq maksimum fərq arasında nums[i] və nums[j] (yəni, nums[j] - nums[i]), belə 0 <= i < j < n və nums[i] < nums[j].

Qayıtmaq bu maksimum fərqƏgər belə olmasa i və j var, qayıt -1.

Nümunələr və izahatlar

Misal 1:

Input: nums = [7,1,5,4]
Output: 4
Explanation:
The maximum difference occurs with i = 1 and j = 2, nums[j] - nums[i] = 5 - 1 = 4.
Note that with i = 1 and j = 0, the difference nums[j] - nums[i] = 7 - 1 = 6, but i > j, so it is not valid.

Misal 2:
Input: nums = [9,4,3,2]
Output: -1
Explanation:
There is no i and j such that i < j and nums[i] < nums[j].

Misal 3:
Input: nums = [1,5,2,10]
Output: 9
Explanation:
The maximum difference occurs with i = 0 and j = 3, nums[j] - nums[i] = 10 - 1 = 9.

Yanaşma

Maksimumu tapa bilərik fərq çıxarsaq ən kiçik ən böyüyündən sayı. Amma ola bilsin ki, ən kiçik rəqəm ən böyüyünün meydana çıxmasından sonra gəlir. Beləliklə, biz hər iki rəqəmi izləyə bilmərik. Gəlin yalnız ən kiçik rəqəmi izləyək. Dəyəri indiyə qədər ziyarət edilən minimum element olacaq minELe dəyişənindən istifadə edin. Maksimum fərqi tapmaq üçün hər bir elementdən bir-bir minEle çıxarın və fərqi başqa res dəyişənində saxlayın. res = -1-i işə salın və 0-dan | ədəd |. Nömrələrin[i] minELe-dən sonra görünməsini təmin etmək üçün res iff nums[i] ≠ minEle-ni yeniləyən res-i yeniləməzdən əvvəl şərt qoya bilərik.

Hər bir element üçün ədədləri tapmaq üçün[i] maksimum ədədlər[i]-rəqəmlər[k] (burada k
belə ki, yalnız massiv və hər iterasiya üzrə təkrarlamaq üçün:
1. maksimum fərq ədədlərini yeniləmək [i]-min lazımdır
2. lazım gələrsə yerli minimumu yeniləyin

Kodu

üçün C++ kodu Artan Elementlər Arasındakı Maksimum Fərq

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int res=-1;
        int minEle=INT_MAX;
        for(int i=0; i<nums.size(); i++) {
            minEle=min(minEle,nums[i]);
            if(nums[i]!=minEle)
                res=max(res,nums[i]-minEle);
        }
        return max(res,-1);
    }
};

Java kodu üçün Artan Elementlər Arasındakı Maksimum Fərq

class Solution {
    public int maximumDifference(int[] nums) {
        int res=-1;
        int minEle = Integer.MAX_VALUE;
        for(int i=0; i<nums.length; i++) {
            minEle = Math.min(minEle,nums[i]);
            if(nums[i]!=minEle)
                res=Math.max(res,nums[i]-minEle);
        }
        return Math.max(res,-1);
    }
}

Artan elementlər arasındakı maksimum fərq üçün mürəkkəblik təhlili LeetCode Həlli

  • Zaman mürəkkəbliyi: O (N)
    • N = verilmiş “nömrələr” massivinin ölçüsü
    • Bütün elementləri ədədlərlə keçmək üçün alqoritmdə bir döngə istifadə olunur
  • Kosmik mürəkkəblik: O (1)
    • Əlavə yer tələb olunmur
Translate »