Наступний Великий Елемент I Рішення Leetcode


Рівень складності Легко
Часто запитують у Амазонка Bloomberg
Стек

Постановка проблеми

У цій задачі ми отримали два списки, у яких перший список є підмножиною другого списку. Для кожного елемента першого списку ми повинні з’ясувати наступний більший елемент у другому списку.

Наступний Великий Елемент I Рішення Leetcode

Приклад

nums1 = [4,1,2], nums2 = [1,3,4,2]
[-1,3,-1]

Пояснення:

для першого елемента list1, тобто для 4, наступного більшого елемента в list2 немає, тому його відповідь -1.
для другого елемента list1, тобто для 1, є 3 більше, ніж 1 у списку 2, отже, його відповідь 3.
для третього елемента list1, тобто для 2, немає наступного більшого елемента в list2, отже, його відповідь -1.

nums1 = [2,4], nums2 = [1,2,3,4]
[3,-1]

Підхід 1 (груба сила)

У цьому підході ми просто знаходимо наступний більший елемент для кожного елемента list1, виконуючи лінійний обхід у list2, використовуючи вкладений цикл for.
Кожен елемент list1 спочатку шукається в list2, а потім шукається його наступний більший елемент. Ми робимо це за допомогою змінної прапора. Для кожного елемента list1 спочатку встановлюється значення false. Коли ми знайшли елемент у list2, для нього встановлюється значення true. Після цього, коли ми знайдемо наступний більший, ми знову встановимо його на false. Роблячи це, ми дізнаємось, що є наступний більший елемент у list2 для цієї змінної або його взагалі немає.

  • Якщо змінна прапора є істинною, це означає, що ми не змогли знайти наступне більше значення для цього елемента.
  • Якщо змінна прапора хибна, це означає, що ми знайшли ще одне велике значення для цього елемента.

Отже, в кінці кожного внутрішнього циклу, відповідно до значення прапора, ми вставимо -1 як нашу відповідь.

Реалізація наступного великого елемента I рішення Leetcode

Програма С ++

#include <iostream>
#include <vector>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        for(int i=0;i<nums1.size();i++){
            bool flag=false;
            for(int j=0;j<nums2.size();j++){
                if(nums1[i]==nums2[j])flag=true;
                if(flag && nums1[i]<nums2[j]){
                    ans.push_back(nums2[j]);flag=false;break;
                }
            }
            if(flag)ans.push_back(-1);
            
        }
        return ans;
    }
int main()
{
    vector<int> nums1{ 4,1,2 }; 
    vector<int> nums2{ 1,3,4,2 }; 
    vector<int>ans=nextGreaterElement(nums1,nums2);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
-1 3 -1

Програма Java

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int[]nums1={4,1,2};
        int[]nums2={1,3,4,2};
        int[]ans=nextGreaterElement(nums1,nums2);
        for(int i:ans){
            System.out.print(i+" ");
        }
            
        
    }
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[]ans=new int[nums1.length];
        for(int i=0;i<nums1.length;i++){
            boolean flag=false;
            for(int j=0;j<nums2.length;j++){
                if(nums1[i]==nums2[j])flag=true;
                if(flag && nums1[i]<nums2[j]){
                    ans[i]=nums2[j];flag=false;break;
                }
            }
            if(flag)ans[i]=-1;
            
        }
        return ans;
    }
}
-1 3 -1

Аналіз складності для наступного великого елемента I рішення Leetcode

Складність часу

O (m * n): Для кожного елемента nums1 ми обводимо nums2 лінійно зліва направо. Таким чином, часова складність становить O (m * n), де m і n - довжина списків.

Складність простору 

O (1): Не використовується зайвий простір (інтервал, що використовується для масиву ans, не враховується, оскільки це необхідно).

Підхід 2 (за допомогою стека)

Цей підхід складається з двох частин.
По-перше, ми використовуємо стек, щоб отримати наступний більший елемент кожного елемента list2 за лінійний час. Наступний більший елемент кожного елемента зберігається в карта.
По-друге, ми збережемо відповідь для кожного елемента list1 у нашому масиві відповідей, використовуючи карту.

Отже, ми обходимо список2 і неодноразово виводимо всі елементи з верхньої частини стека, які менше поточного числа, і одночасно, при кожному вискакуванні ми будемо реєструвати поточний елемент як найближчу більшу відповідь кожного спливаючого елемента. Для цього відображення ми просто використаємо карту.
Тепер у нас є карта, яка є просто відображенням елементів з відповідними наступними більшими елементами.
Нарешті, ми переглянемо список1 і збережемо відповідні значення з карти у нашому списку відповідей.

Реалізація наступного великого елемента I рішення Leetcode

Програма С ++

#include <iostream>
#include <vector>
#include <stack>
#include <map>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int>stack;
        map<int,int>map;
        vector<int>ans;
        for(int i=0;i<nums2.size();i++){
            while(!stack.empty()){
                if(stack.top()<nums2[i]){
                    map.insert(pair<int,int>(stack.top(),nums2[i]));
                    stack.pop();
                }else break;
            }
            stack.push(nums2[i]);
        }
        
        for(int i=0;i<nums1.size();i++){
            int val = map[nums1[i]];
            if(val==0)ans.push_back(-1);
            else ans.push_back(val);
        }
        return ans;
    }
int main()
{
    vector<int> nums1{ 4,1,2 }; 
    vector<int> nums2{ 1,3,4,2 }; 
    vector<int>ans=nextGreaterElement(nums1,nums2);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
-1 3 -1

Програма Java

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int[]nums1={4,1,2};
        int[]nums2={1,3,4,2};
        int[]ans=nextGreaterElement(nums1,nums2);
        for(int i:ans){
            System.out.print(i+" ");
        }
            
        
    }
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer>stack=new Stack<Integer>();
        Map<Integer,Integer>map=new HashMap<Integer,Integer>();
        int[]ans=new int[nums1.length];
        for(int i:nums2){
            while(!stack.isEmpty()){
                if(stack.peek()<i){
                    map.put(stack.peek(),i);
                    stack.pop();
                }else break;
            }
            stack.push(i);
        }
        for(int i=0;i<nums1.length;i++){
            if(map.containsKey(nums1[i]))
            ans[i]=map.get(nums1[i]);
            else ans[i]=-1;
        }
        return ans;
    }
}
-1 3 -1

Аналіз складності для наступного великого елемента I рішення Leetcode

Складність часу

O (m + n): По-перше, ми обходимо list2, щоб знайти наступний більший елемент для всіх елементів list2. Потім ми об’їжджаємо list1, щоб додати відповіді. Отже, складність часу - це сума довжини обох списків.

Складність простору 

O (n): Ми використовуємо карту, щоб знайти відповідь на будь-який ключ за час O (1), отже, складність простору дорівнює O (n).