本文主要是介绍左程云算法 - 公开课笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第五节
题目：原地交换，不允许额外的空间
方法1：复杂度O(N/2)
1、左侧逆序
2、右侧逆序
3、整体逆序
方法2：循环右移
复杂度O(N^2)
方法3：
直到左右等长的时候，就不再交换了
第六节
方法一：暴力
方法二：一种不是最优解的解法：先对绝对值进行排序，再比较前后数字是否相同
方法三：最优解，双指针原理
两头指针，谁的绝对值大，谁动
首尾指针：划过的数字，可以保证以后再也不会出现这个结果
如果只关注所有波峰波谷的话，可能会出现波峰波谷失效的状态。
变换思路：求某一个位置i上方有多少水
暴力解法O(n^2)
怎么找左边和右边最大值？
生成某前缀数组最大值，作为预处理结构：
因为left辅助结构本身就是从左往右遍历的，所以在计算水量遍历时，可以用一个变量维持左侧已经遍历过部分的最大值，就没有必要另外维护一个left数组了，相当于在线计算left数组
彻底不用辅助结构，用双指针，时间复杂度仍为O(n)的解法：
leftmax、rightmax两个最大值，哪边最大值小，结算哪一边的水量。
移动的时候，更新自己一侧的最大值
当左侧最大值小于右侧最大值的时候，结算左侧水量，往右移动；
…
直到最后，两个指针相遇，停止。
对数器验证
这篇关于左程云算法 - 公开课笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
