ໄລຍະທາງສູງສຸດໃນອາເລ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ກູໂກ Oracle
Array Hash

ບັນຫາ "ໄລຍະທາງສູງສຸດໃນອາເລ" ລະບຸວ່າທ່ານຖືກມອບໃຫ້ "n" ບໍ່. ຂອງຂບວນການແລະອາທິປະໄຕທັງ ໝົດ ແມ່ນໃຫ້ຕາມ ​​ລຳ ດັບ. ວຽກງານຂອງທ່ານແມ່ນເພື່ອຊອກຫາຄວາມແຕກຕ່າງສູງສຸດ / ຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຂອງສອງຕົວເລກໃນ array ແລະພວກເຮົາສາມາດ ກຳ ນົດໄລຍະທາງສູງສຸດລະຫວ່າງສອງຕົວເລກຄື abs | ab |. ທ່ານສາມາດເລືອກສອງຕົວເລກເພື່ອປະກອບເປັນແຖວທີ່ແຕກຕ່າງກັນແລະຄົ້ນຫາ abs | ab | ເປັນຄວາມແຕກຕ່າງສູງສຸດ.

ຍົກຕົວຢ່າງ

[  [1,2,3],
[0,2,3],
[1,4,5] ]
5

ຄໍາອະທິບາຍ

ເນື່ອງຈາກວ່າຕົວເລກ '0' ໃນແຖວທີສອງແລະເບີ 5 'ໃນແຖວທີສາມເຮັດໃຫ້ມີຄວາມແຕກຕ່າງກັນສູງສຸດໃນອາເລທັງ ໝົດ.

ລະບົບວິເຄາະ

  1. ປະກາດຜົນໄດ້ຮັບຕົວແປແລະ ກຳ ນົດໃຫ້ 0.
  2. ກຳ ນົດຄ່າຂອງ ຕຳ ່ສຸດທີ່ ປ່ຽນແປງ[0] [0].
  3. ກຳ ນົດຄ່າຂອງສູງສຸດ ຂອງ ຄວາມຍາວຂອງແຖວ ທຳ ອິດເຊັ່ນ: ສູງສຸດ= varray [0] [0th ແຖວຍາວ -1].
  4. ຊອກຫາມູນຄ່າສູງສຸດຂອງຄວາມແຕກຕ່າງລະຫວ່າງອົງປະກອບ ທຳ ອິດຂອງອາເລກັບອົງປະກອບສຸດທ້າຍຂອງອາເລແລະຄວາມແຕກຕ່າງລະຫວ່າງອົງປະກອບສຸດທ້າຍຂອງອາເລກັບອົງປະກອບ ທຳ ອິດຂອງອາເລສອງ
  5. ດັ່ງນັ້ນ, ຊອກຫາມູນຄ່າສູງສຸດລະຫວ່າງມູນຄ່າທີ່ຜະລິດຈາກເສັ້ນຂ້າງເທິງແລະຜົນໄດ້ຮັບແລະເກັບມັນໄວ້ໃນຜົນຜະລິດ.
  6. ຊອກຫາມູນຄ່າທີ່ນ້ອຍກວ່າລະຫວ່າງ ປ່ຽນແປງ [i] [0] ແລະ ຕໍາ່ສຸດທີ່ ແລະກໍານົດໃຫ້ຢູ່ໃນຕໍາ່ສຸດທີ່.
  7. ຊອກຫາມູນຄ່າທີ່ໃຫຍ່ກວ່າລະຫວ່າງ varray [i] [row_size-1] ແລະ ສູງສຸດ ແລະຕັ້ງຄ່າໃຫ້ສູງສຸດ.
  8. ເຮັດເລື້ມຄືນຂະບວນການຂ້າງເທິງນີ້ຈົນກ່ວາໃນຕອນທ້າຍຂອງອາເລໄດ້.
  9. ກັບຄືນຜົນຜະລິດ.

ຄຳ ອະທິບາຍ ສຳ ລັບໄລຍະທາງສູງສຸດໃນອາເລ

ວຽກງານຂອງພວກເຮົາແມ່ນເພື່ອຊອກຫາຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງສູງສຸດລະຫວ່າງສອງຕົວເລກໃນຂບວນທີ່ແຕກຕ່າງກັນ. ພວກເຮົາພຽງແຕ່ສາມາດໃຊ້ຮັງ 'for loop' ແລະເຮັດໃຫ້ມັນງ່າຍໂດຍການຄົ້ນພົບຄວາມແຕກຕ່າງສູງສຸດຂອງຕົວເລກທັງ ໝົດ.

ແຕ່ແທນທີ່ຈະໃຊ້ວົງແຫວນທີ່ມີຮັງແລະຜ່ານສ່ວນປະກອບທັງ ໝົດ ຂອງອາເລ. ພວກເຮົາສາມາດໃຊ້ແບບງ່າຍໆ ສໍາລັບການ loop ແລະມີວິທີແກ້ໄຂທີ່ມີປະສິດຕິພາບ. ນັບຕັ້ງແຕ່ອົງປະກອບທັງ ໝົດ ຖືກຈັດຮຽງຕາມ ລຳ ດັບຕັ້ງຊັນຂຶ້ນໃນແຖວເຂົ້າ. ພວກເຮົາພຽງແຕ່ຕ້ອງການຊອກຫາຄວາມແຕກຕ່າງລະຫວ່າງອົງປະກອບສຸດທ້າຍແລະຄັ້ງ ທຳ ອິດຂອງອາຄານທີ່ແຕກຕ່າງກັນ. ເພາະວ່າມີພຽງແຕ່ສອງ ຕຳ ແໜ່ງ ທີ່ຕັ້ງໄວ້ເທົ່ານັ້ນທີ່ສາມາດໃຫ້ຄວາມແຕກຕ່າງສູງສຸດ. ຫຼັງຈາກທີ່ທັງຫມົດ, ແຕ່ລະອາເລແມ່ນຈັດລຽງແລະອົງປະກອບທໍາອິດແມ່ນສະເຫມີໄປຫນ້ອຍທີ່ສຸດຫຼືຫນ້ອຍທີ່ສຸດໃນບັນດາຄົນອື່ນ. ແລະອົງປະກອບສຸດທ້າຍຈະເປັນຕົວເລກທີ່ໃຫຍ່ທີ່ສຸດຂອງອາເລ.

ສະນັ້ນໃຫ້ພວກເຮົາໃນນີ້ເອົາຕົວຢ່າງແລະແກ້ໄຂມັນ:

ການປ້ອນຂໍ້ມູນ: arr [] [] = {{0,2,4}, {2,3}, {4,5,6}};

ຜົນໄດ້ຮັບ = 0, ສູງສຸດ = 4, ຕ່ ຳ ສຸດ = 0, i = 1

output = std :: max (ຜົນຜະລິດ,

std :: ສູງສຸດ (abs (varray [i] [varray [i] .size () - 1] - ຕໍາ່ສຸດທີ່),

abs (ສູງສຸດ - ຕົວປ່ຽນແປງ [i] [0]))))

ຜົນໄດ້ຮັບແມ່ນເກັບໄວ້ເປັນ 3

ຍັງຄົງຢູ່ສູງສຸດເທົ່າທີ່ມັນຈະເປັນ 4, ຕ່ ຳ ສຸດແມ່ນເທົ່າກັບ 0, i = 2

output = std :: max (ຜົນຜະລິດ,

std :: ສູງສຸດ (abs (varray [i] [varray [i] .size () - 1] - ຕໍາ່ສຸດທີ່),

abs (ສູງສຸດ - ຕົວປ່ຽນແປງ [i] [0]))))

ຄວາມແຕກຕ່າງລະຫວ່າງອົງປະກອບສຸດທ້າຍແລະຄັ້ງ ທຳ ອິດຂອງອາຄານທີ່ແຕກຕ່າງກັນ

0 ແລະ 6 ແລະໃນນັ້ນ 6 ແມ່ນຄວາມແຕກຕ່າງສູງສຸດສະນັ້ນຜົນຜະລິດຈະກາຍເປັນ 6

ແລະສົ່ງຄືນ 6.

ໄລຍະທາງສູງສຸດໃນອາເລ

ໂຄງການ C ++ ສຳ ລັບໄລຍະຫ່າງສູງສຸດໃນອາເລ

#include <iostream>
#include<vector>
#include<cstdlib>
using namespace std;
int getMaxDistance(vector<vector <int>> varray)
{
    int output=0;
    int minimum=varray[0][0];
    int maximum=varray[0][varray[0].size()-1];

    for(int i = 1 ; i < varray.size() ; i++ )
    {
        output=std::max(output, std::max( abs( varray[i][varray[i].size()-1] - minimum ), abs(maximum-varray[i][0]) ) );
        minimum=std::min( minimum, varray[i][0] );
        maximum=std::max( maximum, varray[i][varray[i].size()-1]);
    }
    return output;

}
int main()
{
    vector<vector<int>> vec= {{0,2,4},{2,3,4},{4,5,6}};
    cout<<"Maximum distance is:"<<getMaxDistance(vec);
    return 0;
}
Maximum distance is: 6

Java Program ສຳ ລັບໄລຍະທາງສູງສຸດໃນ Array

import java.util.*;
import java.io.*;

class maximumDistance
{
    public static int getMaxDistance(int array[][])
    {
        int output=0;
        int minimum=array[0][0];
        int maximum=array[0][array[0].length-1];

        for(int i = 1 ; i < array.length ; i++ )
        {
            output=Math.max(output, Math.max(Math.abs( array[i][array[i].length-1] - minimum ), Math.abs(maximum-array[i][0]) ) );
            minimum=Math.min( minimum, array[i][0] );
            maximum=Math.max( maximum, array[i][array[i].length-1]);
        }
        return output;

    }
    public static void main(String args[])
    {
        int arr[][]= {{0,2,4},{2,3},{4,5,6}};
        System.out.println("Maximum distance is:"+(getMaxDistance(arr)));
    }
}
Maximum distance is: 6

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບທີ່ຢູ່ໃນຂບວນ. ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງຂ້າມຜ່ານແຖວແຖວຂອງ 2D array ຫຼືມາຕຣິກເບື້ອງ. ແຕ່ພວກເຮົາບໍ່ເຄີຍຜ່ານຖັນຂອງຕາຕະລາງການຜະລິດເຂົ້າຂອງພວກເຮົາ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ຄົງທີ່. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ໃຊ້ພຽງແຕ່ຕົວປ່ຽນ ຈຳ ນວນເທົ່ານັ້ນ. ວິທີການມີຄວາມສັບສົນໃນພື້ນທີ່ຄົງທີ່.

ເອກະສານ