下一個更大的元素I Leetcode解決方案


難度級別 容易獎學金
經常問 亞馬遜 彭博社

問題陳述

在這個問題中,我們得到兩個列表,其中第一個列表是第二個列表的子集。 對於第一個列表的每個元素,我們必須在第二個列表中找出下一個更大的元素。

下一個更大的元素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(強力)

在這種方法中,我們使用嵌套的for循環在list1中進行線性遍歷,從而為list2的每個元素簡單地找到下一個更大的元素。
首先在list1中搜索list2的每個元素,然後搜索其下一個更大的元素。 我們通過使用標誌變量來做到這一點。 對於list1的每個元素,首先將其設置為false。 在list2中找到元素後,將其設置為true。 之後,當我們找到下一個更大的對象時,將再次將其設置為false。 這樣,我們將了解到list2中該變量還有下一個更大的元素,或者沒有任何元素。

  • 如果flag變量為true,則意味著我們找不到該元素的下一個更大的值。
  • 如果flag變量為false,則意味著我們為該元素找到了下一個更大的值。

因此,在每個內部循環的末尾,根據標誌值,我們將插入-1作為我們的答案。

下一個更大的元素I Leetcode解決方案的實現

C ++程序

#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的每個元素的答案存儲在我們的答案數組中。

因此,我們將遍歷list2並從堆棧頂部重複彈出所有小於當前數量的元素,同時,每次彈出時,我們都會將當前元素記錄為每個彈出元素中最接近的較大答案。 對於此映射,我們將僅使用地圖。
現在,我們有了一個映射,它只是元素與它們各自的下一個更大元素的映射。
最後,我們將遍歷list1並將它們各自的值從map中存儲到我們的答案列表中。

下一個更大的元素I Leetcode解決方案的實現

C ++程序

#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(1)時間內任何鍵的答案,因此空間複雜度為O(n)。