力扣算法打卡刷题|??思维导图整理大厂面试高频数组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.动态规划的构建经过前面几道题目的训练: 最大子序和, 最大子序积, 对于这种求这种最长数组的题目, 我们很容易就能想到利用动态规划来求解.
【力扣算法打卡刷题|??思维导图整理大厂面试高频数组16: 最长湍流子数组的动态规划构建和滑动窗口解法, 力扣978??】但是会发现本题在设计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 滑动窗口的另一个难点在于边界的处理, 对于本题就是窗口长度变为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 = 0while right < n - 1 : if left == right : # 特殊情况: 窗口长度为1 if arr[left] == arr[left + 1] : # 两指针相等时, 左右指针同时移动 left+=1right+=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 = rightret = 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的性能情况和常见后缀的含义思维导图整理