99热精品五月,AV天堂亚洲色图,成人日韩久久

前言

大家好，我是小彭。

今天分享到一種棧的衍生數(shù)據(jù)結(jié)構(gòu) —— 單調(diào)棧（Monotonic Stack）。棧（Stack）是一種滿足后進(jìn)先出（LIFO）邏輯的數(shù)據(jù)結(jié)構(gòu)，而單調(diào)棧實(shí)際上就是在棧的基礎(chǔ)上增加單調(diào)的性質(zhì)（單調(diào)遞增或單調(diào)遞減）。那么，單調(diào)棧是用來(lái)解決什么問(wèn)題的呢？

學(xué)習(xí)路線圖：

1. 單調(diào)棧的典型問(wèn)題

單調(diào)棧是一種特別適合解決 “下一個(gè)更大元素” 問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。

舉個(gè)例子，給定一個(gè)整數(shù)數(shù)組，要求輸出數(shù)組中元素 $i$ 后面下一個(gè)比它更大的元素，這就是下一個(gè)更大元素問(wèn)題。這個(gè)問(wèn)題也可以形象化地思考：站在墻上向后看，問(wèn)視線范圍內(nèi)所能看到的下一個(gè)更高的墻。例如，站在墻 [3] 上看，下一個(gè)更高的墻就是墻 [4] 。

形象化思考

這個(gè)問(wèn)題的暴力解法很容易想到：就是遍歷元素 $i$ 后面的所有元素，直到找到下一個(gè)比 $i$ 更大的元素為止，時(shí)間復(fù)雜度是 $O(n)$ ，空間復(fù)雜度是 $O(1)$ 。單次查詢確實(shí)沒(méi)有優(yōu)化空間了，那多次查詢呢？如果要求輸出數(shù)組中每個(gè)元素的下一個(gè)更大元素，那么暴力解法需要的時(shí)間復(fù)雜度是 $O(n^2)$ 。有沒(méi)有更高效的算法呢？

2. 解題思路

我們先轉(zhuǎn)變一下思路：

在暴力解法中，我們每處理一個(gè)元素就要去求它的 “下一個(gè)更大元素”?，F(xiàn)在我們不這么做，我們每處理一個(gè)元素時(shí)，由于不清楚它的解，所以先將它緩存到某種數(shù)據(jù)容器中。后續(xù)如果能確定它的解，再將其從容器中取出來(lái)。 這個(gè)思路可以作為 “以空間換時(shí)間” 優(yōu)化時(shí)間復(fù)雜度的通用思路。

回到這個(gè)例子上：

在處理元素 [3] 時(shí)，由于不清楚它的解，只能先將 [3] 放到容器中，繼續(xù)處理下一個(gè)元素；
在處理元素 [1] 時(shí)，我們發(fā)現(xiàn)它比容器中所有元素都小，只能先將它放到容器中，繼續(xù)處理下一個(gè)元素；
在處理元素 [2] 時(shí)，我們觀察容器中的 [1] 比當(dāng)前元素小，說(shuō)明當(dāng)前元素就是 [1] 的解。此時(shí)我們可以把 [1] 彈出，記錄結(jié)果。再將 [2] 放到容器中，繼續(xù)處理下一個(gè)元素；
在處理元素 [1] 時(shí)，我們發(fā)現(xiàn)它比容器中所有元素都小，只能先將它放到容器中，繼續(xù)處理下一個(gè)元素；
在處理元素 [4] 時(shí)，我們觀察容器中的 [3] [2] [1] 都比當(dāng)前元素小，說(shuō)明當(dāng)前元素就是它們的解。此時(shí)我們可以把它們彈出，記錄結(jié)果。再將 [4] 放到容器中，繼續(xù)處理下一個(gè)元素；
在處理元素 [1] 時(shí)，我們發(fā)現(xiàn)它比容器中所有元素都小，只能先將它放到容器中，繼續(xù)處理下一個(gè)元素；
遍歷結(jié)束，所有被彈出過(guò)的元素都是有解的，保留在容器中的元素都是無(wú)解的。

分析到這里，我們發(fā)現(xiàn)問(wèn)題已經(jīng)發(fā)生轉(zhuǎn)變，問(wèn)題變成了：“如何尋找在數(shù)據(jù)容器中小于當(dāng)前元素的數(shù)”。現(xiàn)在，我們把注意力集中在這個(gè)容器上，思考一下用什么數(shù)據(jù)結(jié)構(gòu)、用什么算法可以更高效地解決問(wèn)題。由于這個(gè)容器是我們額外增加的，所以我們有足夠的操作空間。

先說(shuō)結(jié)論：

方法 1 - 暴力： 遍歷整個(gè)數(shù)據(jù)容器中所有元素，最壞情況（遞減序列）下所有數(shù)據(jù)都進(jìn)入容器中，單次操作的時(shí)間復(fù)雜度是 $O(N)$ ，整體時(shí)間復(fù)雜度是 $O(N^2)$ ；
方法 2 - 二叉堆： 不需要遍歷整個(gè)容器，只需要對(duì)比容器的最小值，直到容器的最小值都大于當(dāng)前元素。最壞情況（遞減序列）下所有數(shù)據(jù)都進(jìn)入堆中，單次操作的時(shí)間復(fù)雜度是 $O(lgN)$ ，整體時(shí)間復(fù)雜度是 $O(N·lgN)$ ；
方法 3 - 單調(diào)棧： 我們發(fā)現(xiàn)元素進(jìn)入數(shù)據(jù)容器的順序正好是有序的，且后進(jìn)入容器的元素會(huì)先彈出做對(duì)比，符合 “后進(jìn)先出” 邏輯，所以這個(gè)容器數(shù)據(jù)結(jié)構(gòu)用棧就可以實(shí)現(xiàn)。因?yàn)槊總€(gè)元素最多只會(huì)入棧和出棧一次，所以整體的計(jì)算規(guī)模還是與數(shù)據(jù)規(guī)模成正比的，整體時(shí)間復(fù)雜度是 $O(n)$ 。

下面，我們先從優(yōu)先隊(duì)列說(shuō)起。

3. 優(yōu)先隊(duì)列解法

尋找最值的問(wèn)題第一反應(yīng)要想到二叉堆。

我們可以維護(hù)一個(gè)小頂堆，每處理一個(gè)元素時(shí)，先觀察堆頂?shù)脑兀?/p>

如果堆頂元素小于當(dāng)前元素，則說(shuō)明已經(jīng)確定了堆頂元素的解，我們將其彈出并記錄結(jié)果；
如果堆頂元素不小于當(dāng)前元素，則說(shuō)明小頂堆內(nèi)所有元素都是不小于當(dāng)前元素的，停止觀察。

觀察結(jié)束后，將當(dāng)前元素加入小頂堆，堆會(huì)自動(dòng)進(jìn)行堆排序，堆頂就是整個(gè)容器的最小值。此時(shí)，繼續(xù)在后續(xù)元素上重復(fù)這個(gè)過(guò)程。

題解

fun nextGreaterElements(nums: IntArray): IntArray {
    // 結(jié)果數(shù)組 
    val result = IntArray(nums.size) { -1 }
    // 小頂堆
    val heap = PriorityQueue<Int> { first, second ->
        nums[first] - nums[second]
    }
    // 從前往后查詢
    for (index in 0 until nums.size) {
        // while：當(dāng)前元素比堆頂元素大，說(shuō)明找到下一個(gè)更大元素
        while (!heap.isEmpty() && nums[index] > nums[heap.peek()]) {
            result[heap.poll()] = nums[index]
        }
        // 當(dāng)前元素入堆
        heap.offer(index)
    }
    return result
}

我們來(lái)分析優(yōu)先隊(duì)列解法的復(fù)雜度：

時(shí)間復(fù)雜度： 最壞情況下（遞減序列），所有元素都被添加到優(yōu)先隊(duì)列里，優(yōu)先隊(duì)列的單次操作時(shí)間復(fù)雜度是 $O(lgN)$ ，所以整體時(shí)間復(fù)雜度是 $O(N·lgN)$ ；
空間復(fù)雜度： 使用了額外的優(yōu)先隊(duì)列，所以整體的空間復(fù)雜度是 $O(N)$ 。

優(yōu)先隊(duì)列解法的時(shí)間復(fù)雜度從 $O(N^2)$ 優(yōu)化到 $O(N·lgN)$ ，還不錯(cuò)，那還有優(yōu)化空間嗎？

4. 單調(diào)棧解法

我們繼續(xù)分析發(fā)現(xiàn)，元素進(jìn)入數(shù)據(jù)容器的順序正好是逆序的，最后加入容器的元素正好就是容器的最小值。此時(shí)，我們不需要用二叉堆來(lái)尋找最小值，只需要獲取最后一個(gè)進(jìn)入容器的元素就能輕松獲得最小值。這符合 “后進(jìn)先出” 邏輯，所以這個(gè)容器數(shù)據(jù)結(jié)構(gòu)用棧就可以實(shí)現(xiàn)。

這個(gè)問(wèn)題也可以形象化地思考：把數(shù)字想象成有 “重量” 的杠鈴片，每增加一個(gè)杠鈴片，會(huì)把中間小的杠鈴片壓扁，當(dāng)前的大杠鈴片就是這些被壓扁杠鈴片的 “下一個(gè)更大元素”。

形象化思考

解題模板

// 從前往后遍歷
fun nextGreaterElements(nums: IntArray): IntArray {
    // 結(jié)果數(shù)組 
    val result = IntArray(nums.size) { -1 }
    // 單調(diào)棧
    val stack = ArrayDeque<Int>()
    // 從前往后遍歷
    for (index in 0 until nums.size) {
        // while：當(dāng)前元素比棧頂元素大，說(shuō)明找到下一個(gè)更大元素
        while (!stack.isEmpty() && nums[index] > nums[stack.peek()]) {
            result[stack.pop()] = nums[index]
        }
        // 當(dāng)前元素入隊(duì)
        stack.push(index)
    }
    return result
}

理解了單點(diǎn)棧的解題模板后，我們來(lái)分析它的復(fù)雜度：

時(shí)間復(fù)雜度： 雖然代碼中有嵌套循環(huán)，但它的時(shí)間復(fù)雜度并不是 $O(N^2)$ ，而是 $O(N)$ 。因?yàn)槊總€(gè)元素最多只會(huì)入棧和出棧一次，所以整體的計(jì)算規(guī)模還是與數(shù)據(jù)規(guī)模成正比的，整體時(shí)間復(fù)雜度是 $O(N)$ ；
空間復(fù)雜度： 最壞情況下（遞減序列）所有元素被添加到棧中，所以空間復(fù)雜度是 $O(N)$ 。

這道題也可以用從后往前遍歷的寫(xiě)法，也是參考資料中提到的解法。 但是，我覺(jué)得正向思維更容易理解，也更符合人腦的思考方式，所以還是比較推薦小彭的模板（王婆賣瓜）。

解題模板（從后往前遍歷）

// 從后往前遍歷
fun nextGreaterElement(nums: IntArray): IntArray {
    // 結(jié)果數(shù)組
    val result = IntArray(nums.size) { -1 }
    // 單調(diào)棧
    val stack = ArrayDeque<Int>()
    // 從后往前查詢
    for (index in nums.size - 1 downTo 0) {
        // while：棧頂元素比當(dāng)前元素小，說(shuō)明棧頂元素不再是下一個(gè)更大元素，后續(xù)不再考慮它
        while (!stack.isEmpty() && stack.peek() <= nums[index]) {
            stack.pop()
        }
        // 輸出到結(jié)果數(shù)組
        result[index] = stack.peek() ?: -1
        // 當(dāng)前元素入隊(duì)
        stack.push(nums[index])
    }
    return result
}

5. 典型例題 · 下一個(gè)更大元素 I

理解以上概念后，就已經(jīng)具備解決單調(diào)棧常見(jiàn)問(wèn)題的必要知識(shí)了。我們來(lái)看一道 LeetCode 上的典型例題：LeetCode 496.

LeetCode 例題

第一節(jié)的示例是求 “在當(dāng)前數(shù)組中尋找下一個(gè)更大元素” ，而這道題里是求 “數(shù)組 1 元素在數(shù)組 2 中相同元素的下一個(gè)更大元素” ，還是同一個(gè)問(wèn)題嗎？其實(shí)啊，這是題目拋出的煙霧彈。注意看細(xì)節(jié)信息：

兩個(gè)沒(méi)有重復(fù)元素的數(shù)組 nums1和 nums2 ；
nums1 是 nums2 的子集。

那么，我們完全可以先計(jì)算出 nums2 中每個(gè)元素的下一個(gè)更大元素，并把結(jié)果記錄到一個(gè)散列表中，再讓 nums1 中的每個(gè)元素去散列表查詢結(jié)果即可。

題解

class Solution {
    fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
        // 臨時(shí)記錄
        val map = HashMap<Int, Int>()
        // 單調(diào)棧
        val stack = ArrayDeque<Int>()
        // 從前往后查詢
        for (index in 0 until nums2.size) {
            // while：當(dāng)前元素比棧頂元素大，說(shuō)明找到下一個(gè)更大元素
            while (!stack.isEmpty() && nums2[index] > stack.peek()) {
                // 輸出到臨時(shí)記錄中
                map[stack.pop()] = nums2[index]
            }
            // 當(dāng)前元素入隊(duì)
            stack.push(nums2[index])
        }

        return IntArray(nums1.size) {
            map[nums1[it]] ?: -1
        }
    }
}

6. 典型例題 · 下一個(gè)更大元素 II（環(huán)形數(shù)組）

第一節(jié)的示例還有一道變型題，對(duì)應(yīng)于 LeetCode 上的另一道典型題目：503. 下一個(gè)更大元素 II

LeetCode 例題

兩道題的核心考點(diǎn)都是 “下一個(gè)更大元素”，區(qū)別只在于把 “普通數(shù)組” 變?yōu)?“環(huán)形數(shù)組 / 循環(huán)數(shù)組”，當(dāng)元素遍歷到數(shù)組末位后依然找不到目標(biāo)元素，則會(huì)循環(huán)到數(shù)組首位繼續(xù)尋找。這樣的話，除了所有數(shù)據(jù)中最大的元素，其它每個(gè)元素都必然存在下一個(gè)更大元素。

其實(shí)，計(jì)算機(jī)中并不存在物理上的循環(huán)數(shù)組，在遇到類似的問(wèn)題時(shí)都可以用假數(shù)據(jù)長(zhǎng)度和取余的思路處理。如果你是前端工程師，那么你應(yīng)該有印象：我們?cè)趯?shí)現(xiàn)無(wú)限循環(huán)輪播的控件時(shí)，有一個(gè)小技巧就是給控件 設(shè)置一個(gè)非常大的數(shù)據(jù)長(zhǎng)度 ，長(zhǎng)到永遠(yuǎn)不可能輪播結(jié)束，例如 Integer.MAX_VALUE。每次輪播后索引會(huì)加一，但在取數(shù)據(jù)時(shí)會(huì)對(duì)數(shù)據(jù)長(zhǎng)度取余，這樣就實(shí)現(xiàn)了循環(huán)輪播了。

無(wú)限輪播偽代碼

class LooperView {

    private val data = listOf("1", "2", "3")        

    // 假數(shù)據(jù)長(zhǎng)度
    fun getSize() = Integer.MAX_VALUE

    // 使用取余轉(zhuǎn)化為 data 上的下標(biāo)
    fun getItem(index : Int) = data[index % data.size]
}

回到這道題，我們的思路也更清晰了。我們不需要無(wú)限查詢，所以自然不需要設(shè)置 Integer.MAX_VALUE 這么大的假數(shù)據(jù)，只需要 設(shè)置 2 倍的數(shù)據(jù)長(zhǎng)度 ，就能實(shí)現(xiàn)循環(huán)查詢（3 倍、4倍也可以，但沒(méi)必要），例如：

題解

class Solution {
    fun nextGreaterElements(nums: IntArray): IntArray {
        // 結(jié)果數(shù)組 
        val result = IntArray(nums.size) { -1 }
        // 單調(diào)棧
        val stack = ArrayDeque<Int>()
        // 數(shù)組長(zhǎng)度
        val size = nums.size
        // 從前往后遍歷
        for (index in 0 until nums.size * 2) {
            // while：當(dāng)前元素比棧頂元素大，說(shuō)明找到下一個(gè)更大元素
            while (!stack.isEmpty() && nums[index % size] > nums[stack.peek() % size]) {
                result[stack.pop() % size] = nums[index % size]
            }
            // 當(dāng)前元素入隊(duì)
            stack.push(index)
        }
        return result
    }
}

7. 總結(jié)

到這里，相信你已經(jīng)掌握了 “下一個(gè)更大元素” 問(wèn)題的解題模板了。除了典型例題之外，大部分題目會(huì)將 “下一個(gè)更大元素” 的語(yǔ)義隱藏在題目細(xì)節(jié)中，需要找出題目的抽象模型或轉(zhuǎn)變思路才能找到，這是難的地方。

小彭在 20 年的文章里說(shuō)過(guò)單調(diào)棧是一個(gè)相對(duì)冷門的數(shù)據(jù)結(jié)構(gòu)，包括參考資料和網(wǎng)上的其他資料也普遍持有這個(gè)觀點(diǎn)。 ~~單調(diào)棧不能覆蓋太大的問(wèn)題域，應(yīng)用價(jià)值不及其他數(shù)據(jù)結(jié)構(gòu)。~~ —— 2 年前的文章

2 年后重新思考，我不再持有此觀點(diǎn)。我現(xiàn)在認(rèn)為：?jiǎn)握{(diào)棧的關(guān)鍵是 “單調(diào)性”，而棧只是為了配合問(wèn)題對(duì)操作順序的要求而搭配的數(shù)據(jù)結(jié)構(gòu)。我們學(xué)習(xí)單調(diào)棧，應(yīng)該當(dāng)作學(xué)習(xí)單調(diào)性的思想在棧這種數(shù)據(jù)結(jié)構(gòu)上的應(yīng)用，而不是學(xué)習(xí)一種新的數(shù)據(jù)結(jié)構(gòu)。對(duì)此，你怎么看？

下一篇文章，我們來(lái)學(xué)習(xí)單調(diào)性的思想在隊(duì)列上數(shù)據(jù)結(jié)構(gòu)上的應(yīng)用 —— 單調(diào)隊(duì)列

更多同類型題目：

單調(diào)棧	難度	題解
496. 下一個(gè)更大元素 I	Easy	【題解】
1475. 商品折扣后的最終價(jià)格	Easy	【題解】
503. 下一個(gè)更大元素 II	Medium	【題解】
739. 每日溫度	Medium	【題解】
901. 股票價(jià)格跨度	Medium	【題解】
1019. 鏈表中的下一個(gè)更大節(jié)點(diǎn)	Medium	【題解】
402. 移掉 K 位數(shù)字	Medium	【題解】
42. 接雨水	Hard	【題解】
84. 柱狀圖中最大的矩形	Hard	【題解】

參考資料

LeetCode 專題 · 單調(diào)棧 —— LeetCode 出品
LeetCode 題解 · 739. 每日溫度 —— LeetCode 出品
第 9 章 · 單調(diào)棧 —— liweiwei1419 著
單調(diào)棧解決 Next Greater Number 一類問(wèn)題 —— labuladong 著

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

使用單調(diào)棧解決 “下一個(gè)更大元素” 問(wèn)題

使用單調(diào)棧解決 “下一個(gè)更大元素” 問(wèn)題

前言

1. 單調(diào)棧的典型問(wèn)題

2. 解題思路

3. 優(yōu)先隊(duì)列解法

4. 單調(diào)棧解法

5. 典型例題 · 下一個(gè)更大元素 I

6. 典型例題 · 下一個(gè)更大元素 II（環(huán)形數(shù)組）

7. 總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

使用單調(diào)棧解決 “下一個(gè)更大元素” 問(wèn)題

前言

1. 單調(diào)棧的典型問(wèn)題

2. 解題思路

3. 優(yōu)先隊(duì)列解法

4. 單調(diào)棧解法

5. 典型例題 · 下一個(gè)更大元素 I

6. 典型例題 · 下一個(gè)更大元素 II（環(huán)形數(shù)組）

7. 總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av