欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java?C++分別實(shí)現(xiàn)滑動窗口的最大值

 更新時(shí)間:2021年12月10日 15:25:19   作者:林深時(shí)不見鹿  
這篇文章主要介紹了分別通過Java和C++實(shí)現(xiàn)滑動窗口最大值,即給定一個(gè)數(shù)組?nums?和滑動窗口的大小?k,請找出所有滑動窗口里的最大值。感興趣的可以了解一下

1、題目

給定一個(gè)數(shù)組 nums 和滑動窗口的大小 k,請找出所有滑動窗口里的最大值。

示例:

提示:

你可以假設(shè) k 總是有效的,在輸入數(shù)組不為空的情況下,1 ≤ k ≤ 輸入數(shù)組的大小。

2、思路

(單調(diào)隊(duì)列) O(n)

給定一個(gè)數(shù)組 nums 和滑動窗口的大小 k,讓我們找出所有滑動窗口里的最大值。

樣例:

如樣例所示,nums = [1,3,-1,-3,5,3,6,7],k = 3,我們輸出[3,3,5,5,6,7]。

首先,我們可以想到最樸素的做法是模擬滑動窗口的過程,每向右滑動一次都遍歷一遍滑動窗口,找到最大的元素輸出,這樣的時(shí)間復(fù)雜度是O ( n k ) O(nk)O(nk)??紤]優(yōu)化,其實(shí)滑動窗口類似于數(shù)據(jù)結(jié)構(gòu)雙端隊(duì)列,窗口向右滑動過程相當(dāng)于向隊(duì)尾添加新的元素,同時(shí)再把隊(duì)首元素刪除。

如何更快的找到隊(duì)列中的最大值?

其實(shí)我們可以發(fā)現(xiàn),隊(duì)列中沒必要維護(hù)窗口中的所有元素,我們可以在隊(duì)列中只保留那些可能成為窗口中的最大元素,去掉那些不可能成為窗口中的最大元素。

考慮這樣一種情況,如果新進(jìn)來的數(shù)字大于滑動窗口的末尾元素,那么末尾元素就不可能再成為窗口中最大的元素了,因?yàn)檫@個(gè)大的數(shù)字是后進(jìn)來的,一定會比之前先進(jìn)入窗口的小的數(shù)字要晚離開窗口,因此我們就可以將滑動窗口中比其小的數(shù)字彈出隊(duì)列,于是隊(duì)列中的元素就會維持從隊(duì)頭到隊(duì)尾單調(diào)遞減,這就是單調(diào)遞減隊(duì)列。

單調(diào)遞增隊(duì)列

對于隊(duì)列內(nèi)的元素來說:

  1. 在隊(duì)列內(nèi)自己左邊的數(shù)就是數(shù)組中左邊第一個(gè)比自己小的元素。
  2. 當(dāng)被彈出時(shí),遇到的就是數(shù)組中右邊第一個(gè)比自己小的元素 。( 只要元素還在隊(duì)列中,就意味著暫時(shí)還沒有數(shù)組中找到自己右側(cè)比自己小的元素)
  3. 隊(duì)頭到隊(duì)尾單調(diào)遞增,隊(duì)首元素為隊(duì)列最小值。

單調(diào)遞減隊(duì)列

對于隊(duì)列內(nèi)的元素來說:

  1. 在隊(duì)列內(nèi)自己左邊的數(shù)就是數(shù)組中左邊第一個(gè)比自己大的元素。
  2. 當(dāng)被彈出時(shí),遇到的就是數(shù)組中右邊第一個(gè)比自己大的元素 ,只要元素還在隊(duì)列中,就意味著暫時(shí)還沒有數(shù)組中找到自己右側(cè)比自己大的元素。
  3. 隊(duì)頭到隊(duì)尾單調(diào)遞減,隊(duì)首元素為隊(duì)列最大值。

了解了單調(diào)隊(duì)列的一些性質(zhì)以后,對于這道題我們就可以維護(hù)一個(gè)單調(diào)遞減隊(duì)列,來保存隊(duì)列中所有遞減的元素 ,隨著入隊(duì)和出隊(duì)操作實(shí)時(shí)更新隊(duì)列,這樣隊(duì)首元素始終就是隊(duì)列中的最大值。同時(shí)如果隊(duì)首元素在滑動窗口中,我們就可以將其加入答案數(shù)組中。

實(shí)現(xiàn)細(xì)節(jié):

為了方便判斷隊(duì)首元素與滑動窗口的位置關(guān)系,隊(duì)列中保存的是對應(yīng)元素的下標(biāo)。

具體解題過程如下:

初始時(shí)單調(diào)隊(duì)列為空,隨著對數(shù)組的遍歷過程中,每次插入元素前,需要考察兩個(gè)事情:

1、合法性檢查:隊(duì)頭下標(biāo)如果距離i 超過了 k ,則應(yīng)該出隊(duì)。

2、單調(diào)性維護(hù):如果 nums[i] 大于或等于隊(duì)尾元素下標(biāo)所對應(yīng)的值,則當(dāng)前隊(duì)尾再也不可能充當(dāng)某個(gè)滑動窗口的最大值了,故需要隊(duì)尾出隊(duì),始終保持隊(duì)中元素從隊(duì)頭到隊(duì)尾單調(diào)遞減。

3、如次遍歷一遍數(shù)組,隊(duì)頭就是每個(gè)滑動窗口的最大值所在下標(biāo)。

時(shí)間復(fù)雜度分析: 每個(gè)元素最多入隊(duì)出隊(duì)一次,復(fù)雜度為O ( n ) O(n)O(n)。

3、c++代碼

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int>q; //雙端隊(duì)列
        vector<int>res;
        for(int i = 0; i < nums.size(); i++){
            while(q.size() &&  i - k + 1 > q.front())  q.pop_front(); //判斷隊(duì)頭是否在滑動窗口范圍內(nèi)
            while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();//維護(hù)單調(diào)遞減隊(duì)列
            q.push_back(i); //將當(dāng)前元素插入隊(duì)尾
            if(i >= k - 1)  res.push_back(nums[q.front()]); //滑動窗口的元素達(dá)到了k個(gè),才可以將其加入答案數(shù)組中
        }
        return res;
    }
};

4、java代碼

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> queue = new ArrayDeque<>(); //雙端隊(duì)列
        int[] res = new int[n - k + 1];
        for (int i = 0 , j = 0; i < n; i++) {
            //判斷隊(duì)頭是否在滑動窗口范圍內(nèi)
            while (!queue.isEmpty() && i- k + 1 > queue.getFirst())   queue.pollFirst();
            //維護(hù)單調(diào)遞減隊(duì)列
            while (!queue.isEmpty() && nums[i] > nums[queue.getLast()])  queue.pollLast();
            queue.offer(i);    //將當(dāng)前元素插入隊(duì)尾
            //滑動窗口的元素達(dá)到了k個(gè),才可以將其加入答案數(shù)組中
            if( i - k + 1 >= 0) res[j++] = nums[queue.getFirst()];           
        }
        return res;
    }
}

以上就是Java C++分別實(shí)現(xiàn)滑動窗口的最大值的詳細(xì)內(nèi)容,更多關(guān)于Java C++ 滑動窗口最大值的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • struts2通過action返回json對象

    struts2通過action返回json對象

    struts2通過action返回json對象其實(shí)很簡單的,首先我們需要引入jar包,然后在寫一個(gè)簡單的action就好了,接下來通過本文給大家介紹struts2通過action返回json對象的方法,感興趣的朋友一起看看吧
    2016-09-09
  • 如何使用IDEA 搭建 SpringCloud 項(xiàng)目

    如何使用IDEA 搭建 SpringCloud 項(xiàng)目

    所謂微服務(wù),就是要把整個(gè)業(yè)務(wù)模塊拆分成多個(gè)各司其職的小模塊,做到單一職責(zé)原則,不會重復(fù)開發(fā)相同的業(yè)務(wù)代碼,實(shí)現(xiàn)真正意義上的高內(nèi)聚、低耦合,這篇文章主要介紹了如何使用IDEA 搭建 SpringCloud 項(xiàng)目,需要的朋友可以參考下
    2023-11-11
  • 解決IDEA2020.1.2IDEA打不開的問題(最新分享)

    解決IDEA2020.1.2IDEA打不開的問題(最新分享)

    由于idea安裝多了某個(gè)jar,點(diǎn)擊出現(xiàn)讀條后閃退情況,接下來通過本文給大家分享解決IDEA2020.1.2IDEA打不開的問題,非常不錯(cuò),具有一定的參考借鑒價(jià)值,感興趣的朋友跟隨小編一起看看吧
    2020-07-07
  • servlet生命周期_動力節(jié)點(diǎn)Java學(xué)院整理

    servlet生命周期_動力節(jié)點(diǎn)Java學(xué)院整理

    這篇文章主要為大家詳細(xì)介紹了servlet生命周期的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-07-07
  • 利用JAVA反射,讀取數(shù)據(jù)庫表名,自動生成對應(yīng)實(shí)體類的操作

    利用JAVA反射,讀取數(shù)據(jù)庫表名,自動生成對應(yīng)實(shí)體類的操作

    這篇文章主要介紹了利用JAVA反射,讀取數(shù)據(jù)庫表名,自動生成對應(yīng)實(shí)體類的操作,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-08-08
  • 詳解如何保證Java本地緩存的一致性

    詳解如何保證Java本地緩存的一致性

    所謂的一致性是指在同時(shí)使用緩存和數(shù)據(jù)庫的場景下,要確保數(shù)據(jù)在緩存與數(shù)據(jù)庫中的更新操作保持同步,那么,怎么保證Java本地緩存的一致性?所以本文將給大家介紹了如何保證Java本地緩存的一致性,需要的朋友可以參考下
    2024-01-01
  • Springboot處理異常的常見方式

    Springboot處理異常的常見方式

    SpringBoot框架異常處理有多種處理方式,今天就帶大家了解一下常見的springboot異常處理方式,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下
    2021-06-06
  • Mybatis返回單個(gè)實(shí)體或者返回List的實(shí)現(xiàn)

    Mybatis返回單個(gè)實(shí)體或者返回List的實(shí)現(xiàn)

    這篇文章主要介紹了Mybatis返回單個(gè)實(shí)體或者返回List的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-07-07
  • Spring?Boot監(jiān)控SQL運(yùn)行情況的全過程

    Spring?Boot監(jiān)控SQL運(yùn)行情況的全過程

    這篇文章主要給大家介紹了關(guān)于Spring?Boot監(jiān)控SQL運(yùn)行情況的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用SpringBoot具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2022-02-02
  • Jasypt對SpringBoot配置文件加密

    Jasypt對SpringBoot配置文件加密

    數(shù)據(jù)庫密碼直接明文寫在配置中,對安全來說,是一個(gè)很大的挑戰(zhàn)。一旦密碼泄漏,將會帶來很大的安全隱患。尤其在一些企業(yè)對安全性要求很高,因此我們就考慮如何對密碼進(jìn)行加密。本文著重介紹Jasypt對SpringBoot配置文件加密。
    2021-05-05

最新評論