??思維導圖整理大廠面試高頻陣列16: 最長湍流子陣列的動態規劃構建 和 滑動視窗解法, 力扣978??

此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.

目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).

關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.

想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!

文章目錄

• • 0.導圖整理
  • 1.動態規劃的構建
  • 2.滑動視窗的各種情況
  • 原始碼
  • • Python:
    • java:

題目鏈接: https://leetcode-cn.com/problems/longest-turbulent-subarray/solution/si-wei-dao-tu-zheng-li-dong-tai-gui-hua-bswtn/

0.導圖整理

1.動態規劃的構建

經過前面幾道題目的訓練: 最大子序和, 最大子序積, 對于這種求這種 最長陣列 的題目, 我們很容易就能想到利用 動態規劃 來求解.

但是會發現本題在設計dp陣列的時候似乎并不像前面兩題那么容易, 最困難的點在于: 湍流子陣列的形成條件正好是完全相反的兩種狀態, 而我們想要用一個dp陣列來同時表示這兩種狀態顯然是不現實的, 所以本題我們必須用兩個dp陣列分別表示不同的狀態, 這樣才能不斷的遞推下去.

兩個dp陣列的定義 和 遞推公式 如下:

我們在定義dp陣列的名字的時候, 盡量能夠直接反映出dp陣列的含義up[i],down[i], 這樣在撰寫代碼的時候一目了然, 不要像官方的定義那樣dp[i][0],dp[i][1], 自己看到后都要考慮是什么含義.

關于遞推公式, 因為湍流子陣列的增長和降低是交替的, 所以當前狀態的上一個狀態的dp陣列必然是相反的. 具體的動態演示程序可以看相應的視頻講解.

其次, 需要注意的點就是 遞推公式中的置一操作. 如下圖所示: 我們看陣列中的第四個數字10, 從它前面的數字2到10是上升的, 所以我們利用down[i-1]更新up[i]的值, 但是對于此時的down[i]只有數字10滿足要求, 之前的數字都是不滿足的, 所以它的值是1.

在撰寫代碼時沒有太大的難度, 但是在進行空間優化的時候, 我們上面提到的置一操作就非常重要了. 沒進行空間優化時, dp陣列是用一個陣列來存盤的, 并且初值都是1, 其實這時在代碼中有沒有置一的操作對于最終的結果都是沒有影響的. 但是空間優化之后, dp陣列只是用一個變數來進行存盤, 它的值是持續改變的, 如果沒有及時的置一操作, 最侄訓得的結果肯定是錯誤的.

2.滑動視窗的各種情況

這題也是可以用 滑動視窗 的思想解決的, 滑動視窗最困難的點在于確定視窗兩端滑動的條件.

對于右指標滑動的兩個條件很好理解, 就是兩種滿足要求的情況. 對于左指標滑動的條件當然就是不滿足的情況了, 但是這里有個注意點: 左指標并不是一個單位一個單位的滑動的, 而是直接跳到右指標的位置. 因為當left<right 時, [left,right+1] 也無法構成「湍流子陣列」, 中間的所有的數必然都是不滿足的, 所以也不需要一個一個的滑動了.

滑動視窗的另一個難點在于 邊界的處理, 對于本題就是視窗長度變為1的情況(即left 和 right 相等的情況)：這時只要arr[right]≠arr[right+1], 就可以將 right 右移一個單位；否則, left 和 right 都要同時右移, 跳過兩個數相等的情況, 對于邊界條件一定要考慮仔細, 不然很容易會出錯的.

原始碼

Python:

# 1.動態規劃
# 未進行空間優化
class Solution(object):
    def maxTurbulenceSize(self, arr: List[int]):
        N = len(arr)
        up = [1] * N   # 以位置 i 結尾的,并且 arr[i - 1] < arr[i] 的最長湍流子陣列長度
        down = [1] * N # 以位置 i 結尾的,并且 arr[i - 1] > arr[i] 的最長湍流子陣列長度
        res = 1
        for i in range(1, N):
            if arr[i - 1] < arr[i]:  # 湍流子陣列的增長和降低是交替的
                up[i] = down[i - 1] + 1
                down[i] = 1
            elif arr[i - 1] > arr[i]:
                up[i] = 1
                down[i] = up[i - 1] + 1
            else:
                up[i] = 1
                down[i] = 1
            res = max(res, up[i], down[i])
        return res

# 空間優化
class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        down, up = 1, 1 # 以此元素結尾的且為谷/峰的最長連續子陣列長度
        res = 1
        for i in range(1, len(arr)):
            if arr[i-1] > arr[i]:
                down = up + 1
                up = 1
            elif arr[i-1] < arr[i]:
                up = down + 1
                down = 1
            else:
                down, up = 1, 1
            res = max(res, down, up)
        return res
        
# 2.滑動視窗
class Solution(object):
    def maxTurbulenceSize(self, arr: List[int]):
        n = len(arr)
        ret = 1
        left = right = 0

        while right < n - 1 :
            if left == right : # 特殊情況: 視窗長度為1
                if arr[left] == arr[left + 1] : # 兩指標相等時, 左右指標同時移動
                    left+=1
                
                right+=1 # 兩指標不相等時, 只移動右指標
            else :  # 正常情況: 視窗長度不為1
                # 下面的兩種情況下, 可以移動右指標擴大視窗
                if arr[right - 1] < arr[right] and arr[right] > arr[right + 1] :
                    right+=1
                elif arr[right - 1] > arr[right] and arr[right] < arr[right + 1] :
                    right+=1
                else : # 不滿足時,[left,right+1]也無法構成湍流子陣列,直接將left移到right
                    left = right               
            
            ret = max(ret, right - left + 1)
        return ret

java:

// 1.動態規劃
class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int res = 1, up = 1, down = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] < arr[i]) {
                up = down + 1;
                down = 1;
            } else if (arr[i - 1] > arr[i]) {
                down = up + 1;
                up = 1;
            } else {
                up = 1;
                down = 1;
            }
            res = Math.max(res, Math.max(up, down));
        }
        return res;
    }
}

// 2.滑動視窗
class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int ret = 1;
        int left = 0, right = 0;


        while (right < n - 1) {
            if (left == right) { // 特殊情況: 視窗長度為1
                if (arr[left] == arr[left + 1]) { // 兩指標相等時, 左右指標同時移動
                    left++;
                }
                right++; // 兩指標不相等時, 只移動右指標
            } else {  // 正常情況: 視窗長度不為1
                // 下面的兩種情況下, 可以移動右指標擴大視窗
                if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
                    right++;
                } else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
                    right++;
                } else { // 不滿足時,[left,right+1]也無法構成湍流子陣列,直接將left移到right
                    left = right;
                }
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }
}

我的更多精彩文章鏈接, 歡迎查看

各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)

力扣演算法刷題 根據思維導圖整理筆記快速記憶算法重點內容(歡迎和博主一起打卡刷題哦)

計算機專業知識 思維導圖整理

最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)

最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目

最值得收藏的 計算機網路 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介

最值得收藏的 演算法分析與設計 全部知識點思維導圖整理(北大慕課課程)

最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理

最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)

最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)

最值得收藏的 數字影像處理 全部知識點思維導圖整理(武漢大學慕課課程)

紅黑樹 一張導圖解決紅黑樹全部插入和洗掉問題 包含詳細操作原理 情況對比

各種常見排序演算法的時間/空間復雜度 是否穩定 演算法選取的情況 改進 思維導圖整理

人工智能課件 演算法分析課件 Python課件 數值分析課件 機器學習課件 影像處理課件

考研相關科目 知識點 思維導圖整理

考研經驗–東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)

東南大學 軟體工程 906 資料結構 C++ 歷年真題 思維導圖整理

東南大學 軟體工程 復試3門科目歷年真題 思維導圖整理

最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理

最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理

高等數學 中值定理 一張思維導圖解決中值定理所有題型

考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記

Python相關技術 知識點 思維導圖整理

Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理

Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理

Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理

PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理

Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理

Java相關技術/ssm框架全部筆記

Spring springmvc Mybatis jsp

科技相關 小米手機

小米 紅米 歷代手機型號大全 發布時間 發布價格

常見手機品牌的各種系列劃分及其特點

歷代CPU和GPU的性能情況和常見后綴的含義 思維導圖整理