Stock III Leetcode шийдлийг худалдаж авах, борлуулах хамгийн тохиромжтой цаг


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Adobe Амазоны
Array Динамик програмчлал

Асуудлын мэдэгдэл

“III хувьцаа худалдаж авах, борлуулах хамгийн тохиромжтой цаг” гэсэн дугаарт массивын элемент бүр тухайн хувьцааны тухайн өдрийн үнийг агуулсан массивыг өгсөн болно.

Тодорхойлолт ажил гүйлгээ нь нэг хувьцаа худалдаж авч, тэр нэг хувьцааг зарж байгаа явдал юм.

Бидний даалгавар бол дараахь хязгаарлалтын дагуу хамгийн их ашиг олох явдал юм.

  1. Өмнөх хувьцаагаа зараагүй бол бид шинэ хувьцаа худалдаж авах боломжгүй. нэг цагт бид хамгийн ихдээ нэг хувьцаа авах боломжтой.
  2. бид хамгийн ихдээ хоёр гүйлгээ хийх боломжтой.

Жишээ нь

prices = [1,2,3,4,5]
4

Тайлбар: авч болох хамгийн их ашиг нь 4. Гүйлгээний дэлгэрэнгүйг дор харуулав.

Эхний өдөр: худалдаж аваарай

Хоёр дахь өдөр: амрах

Гурав дахь өдөр: амрах

Дөрөв дэх өдөр: амрах

Тав дахь өдөр: зарах

Хувьцаа III Leetcode шийдлийг худалдаж авах, борлуулах хамгийн тохиромжтой цаг хугацаа

Энэ асуудал нь илүү хэцүү хувилбар юм Хувьцаа худалдаж авах, борлуулах хамгийн тохиромжтой цаг. Тиймээс энэ асуудал руу үсрэхээсээ өмнө асуудлын хялбар хувилбарыг шийдэх ёстой.

Энд зөвхөн нэг гүйлгээ хийх боломжтой хялбар хувилбартай харьцуулахад бид хамгийн ихдээ хоёр гүйлгээ хийх боломжтой. Энэ нь хамгийн их ашиг өгөх байдлаар нэг гүйлгээ эсвэл хоёр гүйлгээ гэсэн үг юм.

Асуудлын хамгийн зальтай хэсэг бол хоёр дахь гүйлгээг хэрхэн яаж хийх вэ гэдэг юм. Энэ асуудлыг харахын тулд үзэл бодлоо өөрчилсний дараа энэ асуудлыг энэ асуудлын хялбар хувилбар болгон хувиргаж болно.

Эхний гүйлгээгээ 200 рупийн ашигтай хийж дуусгалаа гэж бодъё. (Энэ хэсэг нь адилхан байна Хувьцаа худалдаж авах, борлуулах хамгийн тохиромжтой цаг). Тиймээс эхний гүйлгээ хийсний дараа бидний гарт 200 Rs байна.

Одоо бид 500 рупийн хувьцаа худалдаж авахаар явахдаа. Хувьцааны үнэ 500 Rs байгаа ч гэсэн бид үүнийг ингэж бодож болно. Гэхдээ бидний хувьд энэ нь 300 Rs юм, яагаад гэвэл бидний гарт аль хэдийн 200 Rs байгаа бөгөөд бид үнэгүй авсан. Одоо бид хоёр дахь гүйлгээгээ цэвэр ашгийг хамгийн их байлгах арга замаар хийх болно Хувьцаа худалдаж авах, борлуулах хамгийн тохиромжтой цаг асуудал.

Энэ жишээнээс хандлага илүү тодорхой болно:

leetcode шийдэл III хувьцааг худалдаж авах, борлуулах хамгийн тохиромжтой цаг

Хэрэгжүүлэх

Хувьцаа худалдаж авах, борлуулахад хамгийн тохиромжтой цаг болох Java код

import java.util.Arrays; 
public class Tutorialcup {
    public static int maxProfit(int[] prices) {
  int firstSell = 0;
  int secondSell = 0;
  int firstBuy = Integer.MAX_VALUE;
  int secondBuy = Integer.MAX_VALUE;
  for(int i = 0; i < prices.length; i++) {
    int p = prices[i];
    firstBuy = Math.min(firstBuy, p);
    firstSell = Math.max(firstSell, p - firstBuy);
    secondBuy = Math.min(secondBuy, p - firstSell);
    secondSell = Math.max(secondSell, p - secondBuy);
  }
  
  return secondSell;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
4

III хувьцааг худалдаж авах, борлуулах хамгийн тохиромжтой цаг үеийн C ++ код

#include <bits/stdc++.h> 
using namespace std; 
     int maxProfit(vector<int>& prices) {
  int firstSell = 0;//stores profit after one sell
  int secondSell = 0;//stores profit after two sell
  int firstBuy = INT_MAX;
  int secondBuy = INT_MAX;
  int n=prices.size();
        for(int i=0;i<n;i++)
        {
            firstBuy=min(firstBuy,prices[i]);
            firstSell=max(firstSell,prices[i]-firstBuy);
            secondBuy=min(secondBuy,prices[i]-firstSell);
            secondSell=max(secondSell,prices[i]-secondBuy); 
        }
        return secondSell;
    }
int main() 
{ 
 vector<int> arr = { 1,2,3,4,5 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
4

III хувьцааны Leetcode шийдлийг худалдаж авах, борлуулах хамгийн сайн цагийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Дээрх кодын цаг хугацааны нарийн төвөгтэй байдал нь O (N) Учир нь бид үнийн массивыг ганц л удаа туулж байна. Энд n нь үнийн массивын урт юм.

Сансрын нарийн төвөгтэй байдал

Дээрх кодын орон зайн нарийн төвөгтэй байдал нь O (1) Учир нь бид зөвхөн хариултыг хадгалахын тулд санах ой ашигладаг.

Ашигласан материал