Altarray diapazonlarının cəmi Leetcode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur AmazonBaxılıb 32

Problem bəyanat

The Altarray diapazonlarının cəmi Leetcode həlli – sizə tam ədəd verildiyini bildirir nömrə of maksimum ölçü 10^3. Verilmiş massivin bütün alt massiv diapazonlarının cəmini qaytarmalıyıq.

The altmasvinin diapazonu altmasvinin ən böyük və ən kiçik elementi arasındakı fərq kimi müəyyən edilir.

Misal:

Altarray diapazonlarının cəmi Leetcode HəlliPin

 

Input: nums = [1,2,3]
Output: 4

Explanation:

  • Bütün alt massivlər [1], [1,2], [1,2,3], [2], [2,3], [3]-dir.
  • Bütün müvafiq alt massivlərin Maksimum və Minimum elementləri [1,1], [1,2], [1,3], [2,2], [2,3], [3,3], burada [min_element, maksimum_element].
  • Alt massivlərin maksimum və minimum elementləri arasındakı fərqlər bunlardır:- [0], [1], [2], [0], [1], [0].
  • Yuxarıdakı bütün dəyərlərin cəmi:- 1+2+1 = 4
Input: [4,-2,-3,4,1]
Output: 59

Explanation:

Yanaşma

Fikir 1:

  1. Qeyd edin ki massivin maksimum ölçüsü 10^3-dir, buna görə də problemi həll edirik O(N^2) vaxtı.
  2. Kobud qüvvə yanaşmasında hər bir alt massivi nəzərdən keçirin və alt massivin minimum elementi ilə yanaşı maksimumunu tapın və maksimum və minimum dəyər arasındakı bütün fərqləri yekunlaşdırın.

Fikir 2:

  1. Bu problemi həll etmək üçün əsas fikir xətti vaxt istifadə etməkdir Yığın.
  2. Tapmaq növbəti böyük element və növbəti kiçik element hər massiv dəyərinin solunda və sağında indekslər.
  3. İndi hər i massiv indeksi üçün bu dəyər diapazonda maksimum və ya minimum olaraq qalır [sol[i]+1, sağ[i]+1], burada sol[i] = i-nin solundakı ilk kiçik/böyük elementin indeksi və sağ[i] = i-nin sağındakı ilk kiçik/böyük elementin indeksi.
  4. Cavabı artırın element*aralığın uzunluğu maksimum halda, cavabı uzunluğu ilə azaldarkən element*aralığın uzunluğu minimum halda. Qeyd edək ki, maksimum və minimum halda diapazonlar fərqli olacaq.
  5. Bu yazının sonunda xətti vaxt kodunu yoxlayın.

Kodu

C++ Altsətir diapazonlarının cəmi O(N^2) Vaxt Leetcode Həlli İdeya 1 əsasında:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long ans = 0,n = nums.size();
        for(int i=0;i<n;i++){
            int mx = INT_MIN,mn = INT_MAX;
            for(int j=i;j<n;j++){
                mx = max(mx,nums[j]);
                mn = min(mn,nums[j]);
                
                ans += mx-mn;
            }
        }
        return ans;
    }
};

Ideya 2-ə əsaslanan O(N^1) Zaman Leetcode Həlli Alt Dizilik diapazonlarının Java cəmi:

class Solution {
    public long subArrayRanges(int[] nums) {
        long ans = 0;
        for(int i=0;i<nums.length;i++){
            int maxi = nums[i],mini = nums[i];
            for(int j=i+1;j<nums.length;j++){
                mini = Math.min(mini,nums[j]);
                maxi = Math.max(maxi,nums[j]);
                ans = ans + (maxi-mini);
            }
        }
        return ans;
    }
}

C++ Altsətir diapazonlarının cəmi O(N) vaxtı Leetcode İdeya 2-ə əsaslanan Həlli:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        int n = nums.size();
        vector<int> left_greater(n,-1),right_greater(n,n);
        vector<int> left_smaller(n,-1),right_smaller(n,n);
        stack<int> s1,s2,s3,s4;
        for(int i=0;i<n;i++){
            while(!s1.empty() and nums[s1.top()]<nums[i]){
                right_greater[s1.top()] = i;
                s1.pop();
            }
            s1.push(i);
        }        
        for(int i=n-1;i>=0;i--){
            while(!s2.empty() and nums[s2.top()]<=nums[i]){
                left_greater[s2.top()] = i;
                s2.pop();
            }
            s2.push(i);
        }        
        for(int i=0;i<n;i++){
            while(!s3.empty() and nums[s3.top()]>nums[i]){
                right_smaller[s3.top()] = i;
                s3.pop();
            }
            s3.push(i);
        }
        for(int i=n-1;i>=0;i--){
            while(!s4.empty() and nums[s4.top()]>=nums[i]){
                left_smaller[s4.top()] = i;
                s4.pop();
            }
            s4.push(i);
        }
        long long ans = 0;
        for(int i=0;i<n;i++){
            long long maxi = (right_greater[i] - i) * (i - left_greater[i]);
            long long mini = (right_smaller[i] - i) * (i - left_smaller[i]);
            ans += (maxi*nums[i]);
            ans -= (mini*nums[i]);
        }        
        return ans;
    }
};

Altarray diapazonlarının cəmi üçün mürəkkəblik təhlili Leetcode Həlli

Zamanın mürəkkəbliyi

1-ci ideyaya əsaslanan kodun zaman mürəkkəbliyi O (N ^ 2) çünki biz O(N^2) vaxtını alan hər bir alt massivi nəzərdən keçiririk.

Həmçinin, 2-ci ideyaya əsaslanan kodun vaxt mürəkkəbliyi O (N) çünki biz O(N) xətti vaxtı alan növbəti böyük/kiçik elementi tapmaq üçün yığından istifadə edirik.

Kosmik Mürəkkəblik

İdeya 1-ə əsaslanan kodun məkan mürəkkəbliyi O (1) çünki biz hər dəfə dəyişənlərlə işləyirik.

İdeya 2-ə əsaslanan kodun məkan mürəkkəbliyi O (N) çünki biz növbətinin indekslərini saxlamaq üçün xətti vektordan istifadə edirik böyük və kiçik element hər indeksdən.

Şərh yaz

Translate »