Գնման և վաճառքի լավագույն ժամանակը II Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon ԴԵ Շոուն facebook Microsoft Morgan Stanley Uber
Դասավորություն Ագահ

Խնդրի հայտարարություն

«II բաժնետոմս գնելու և վաճառելու լավագույն ժամանակը» խնդրում մեզ տրվում է զանգված, որտեղ զանգվածի յուրաքանչյուր տարր պարունակում է տվյալ բաժնետոմսի գինը այդ օրը:

Սահմանումը գործարքը գնում է մեկ բաժնետոմսի բաժնետոմս և վաճառում այդ մեկ բաժնետոմս:

Մեր խնդիրն է գտնել առավելագույն շահույթը հետևյալ սահմանափակումների ներքո.

  1. մենք չենք կարող գնել նոր բաժնետոմս, եթե չենք վաճառել նախորդ բաժնետոմսերը: դա այն ժամանակ, երբ մենք կարող ենք ունենալ առավելագույնը մեկ բաժնետոմս:
  2. մենք կարող ենք կատարել այնքան գործարք, որքան ցանկանում ենք:

Օրինակ

prices = [7,1,5,3,6,4]
7

Բացատրությունը. առավելագույն շահույթը, որը կարելի է ձեռք բերել, կազմում է 7. Հետևյալը գործարքի մանրամասներն են.

Առաջին օրը `հանգստանալ

Երկրորդ օրը `գնել

Երրորդ օրը `վաճառել

Չորրորդ օրը `գնել

Հինգերորդ օր ՝ վաճառել

Վեցերորդ օր. Հանգիստ

Գնման և վաճառքի ֆոնդային II Leetcode լուծում լավագույն ժամանակի մոտեցում

Քանի որ մենք գործարքների քանակի վերաբերյալ որևէ սահմանափակում չունենք, մենք կմտածենք ա ագահ ալգորիթմ այստեղ Այնպես որ, ամեն անգամ մենք բաժնետոմս կգնենք նվազագույն գնով և կվաճառենք այն առավելագույն գնով: Կարող ենք ամփոփել, քանի որ յուրաքանչյուր մինիմումի դեպքում մենք բաժնետոմս կգնենք, և յուրաքանչյուր մաքսիմում `կվաճառենք բաժնետոմս: Սա բացատրվում է ստորև բերված նկարում: Դա սյուժե է բաժնետոմսի գնի և օրերի միջև: leetcode- ի լուծում II- ի գնման և վաճառքի լավագույն ժամանակի համար

Մենք կարող ենք դա ավելի պարզ դարձնել, եթե նկատենք, որ առավելագույնները ստեղծվում են, երբ նվազագույններին փոքր արժեքներ են ավելանում: Այնպես որ, չնայած առավելագույն շահույթը հաշվարկելու յուրաքանչյուր նվազագույնին և առավելագույնին հետևելուն, մենք կարող ենք ուղղակիորեն մեր շահույթին ավելացնել այդ արժեքները, որոնց համար մենք գտել ենք դրական թեքություն, այսինքն ՝ գներ [i]> գներ [i-1]: Նման բոլոր արժեքների ավելացումը մեզ առավելագույն շահույթ կտա:

leetcode- ի լուծում II- ի գնման և վաճառքի լավագույն ժամանակի համար

Իրականացման

C ++ կոդ II ֆոնդային գնման և վաճառքի լավագույն ժամանակի համար

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 7,1,5,3,6,4 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
7

Java ֆոնդային ֆոնդային բորսա գնելու և վաճառելու լավագույն ժամանակը

import java.util.Arrays; 
public class Tutorialcup {
     public static int maxProfit(int[] prices) {
        int ans = 0;
        int n=prices.length;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
  public static void main(String[] args) {
    int [] arr = {7,1,5,3,6,4}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
7

II Leetcode լուծում գնելու և վաճառելու լավագույն ժամանակի բարդության վերլուծություն

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n) քանի որ մենք միայն մեկ անգամ ենք անցնում գների զանգվածը: Այստեղ n- ը գնի զանգվածի երկարությունն է:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք հիշողությունը օգտագործում ենք միայն պատասխանը պահելու համար:

Սայլակ