leetcode hot100_part02_双指针

283.移动零

. - 力扣（LeetCode）；当前遍历位置不为0，左右指针一起前进，前进到为0的位置，左指针停下，右指针继续前进，右指针直到前进到第一个不为0的位置，然后交换，再一起前进；

11.盛水最多的容器

        偷看了一下评论区的小提示写出来的，头尾双指针往中间移动，怎么移动？用贪心，尽可能的往能够使面积更大的方向移动。最长递增子序列的第二个方法用的也是贪心。体会到了。能靠近就靠近一点。

        暂时还没看官方的解法，就是首尾往中间移，怎么移动？尽可能往面积大的朝向。

        往中间移长度肯定是减小，如果想面积S大肯定是要高度变高，S肯定是取决于高的那个，所以我们先找出两边中矮的那个，让它往中间移动，移动的结果肯定是要变高才有效，才有可能使面积变大，否则S肯定减小。

        想一想为什么一定要移动矮的，移动高的向中间靠近不行吗？（不行，分类讨论一下就行，移动高的，无论移动后高度变高还是变矮，s都变小）

        所以让两边里矮的移动，每移动一步判断是否变高，变高了就计算结果迭代比较；没有变高就继续移动。因为往里移动时只要矮的变高才有可能使S变大。

        官方的思路不够简洁，每次矮的只移动一个，可以直接让矮的往里移动到第一个比它大的位置。

9/12

        看了上面之前的思路，我觉得没啥要补充了；所以往更大的方向移动，双指针何尝不是一种贪心呢

15.三数之和

        视频讲的很通透：两数之和 三数之和【基础算法精讲 01】_哔哩哔哩_bilibili

        对于两数之和||，一个递增排好序的数组，找到两个不同下标的数使其和为target；l和r分别指向index = 0 和 len -1；如果当前和>target，r--；小于target, l++；关键是时间复杂度从O(n^2)降为O(n)

        三数之和就是遍历每个数，让它成为target；先排序后用上面同样的方法；时间复杂度O(n^2)

        注意三个数的下标不同，还有就是不能出现重复的结果（重复的三个数）；代码写的时候发生了几个错误；想想三个下标的范围，还有就是相等情况下l++r--写成l++r++；你不越界谁越界

42.接雨水

还有接雨水II呢。

9/12

官方解法

代码参考：. - 力扣（LeetCode）

单调栈

        感觉很难想啊，把抽象的做法用易于理解的语言表述出来；. - 力扣（LeetCode）的解法5；

        我们用栈保存每堵墙（每个height[i]）；当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。

        如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。

总体的原则：

• 当前高度小于等于栈顶高度，入栈，指针后移。
• 当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。

        关于每个坑位面积的叠加，是横着算的，因为对于i位置来说，我们当前的位置是i之后第一个比i大的，不细说了，不懂看灵山视频吧

前后缀

        在滑动窗口最大值的第三种解法，也是前后缀；回忆一下；

        我们用 leftMax[i] 表示下标 i 之前，包括下标 i 的数组元素最大值，rightMax[i]表示下标 i 之后包括下标 i 的数组元素最大值；为什么定义这两个数组呢？我们把每个位置 i 看做一个竖直方向的水桶；那么水桶的左右高度就是leftMax[i]和rightMax[i]；单个水桶的宽为1，减去高度就是每个水桶的水；叠加就行；

双指针（前后缀优化）

        是前后缀的一个优化方案，这个方法中我们不需要再定义前后缀数组，而是用preMax和sufMax表示 l 和 r 指针走过的前缀和后缀的最大值（实时性）代替前后缀数组；

        l 和 r 分别初始化为数组元素的头和尾，想象一下数组的坑中没有水，然后下起了小雨，对于某个坑位 i 能接到的雨水最大值；

       如果当前 l 就在 i 位置，且preMax < sufMax；由于短板效应，l位置水桶能接多少雨水取决于preMax；为什么？虽然不知道 l + 1 位置的高度，但是 r 指针遍历到的当前的sufMax已经大于 l 的preMax；

        l~r 之间的柱子的高度h如果小于sufMax，那么l位置有sufMax这个右边的高度进行兜底（想象所有坑都接满的状态），h如果大于sufMax就更不用说了；

        所以当当前 l 就在 i 位置，且preMax < sufMax，我们就可以算出这个坑的雨水；同理当前r在 i 位置，且preMax > sufMax，我们也可以算出 r 位置的雨水量；并在这两种情况计算完后分别移动l , r；直至相遇遍历完所有的坑位；

4/14

双向遍历

        这个思路好像来源于之前，只记得那个最长括号匹配的题目了。首先想到的是计算每个可能接到雨水的坑。

        先从头开始遍历，fast比low领先一个位置，fast肯定要移动到大于等于low的位置才能接到雨水，当fast到了第一个比low大的位置时停下，在这个遍历期间记录了比low小的位置之和，求面积的时候减去，得到一个坑位的雨水量。然后low移动到fast的位置（折叠了起来），fast设置为其后的一个位置，继续求坑位的雨水量。

        那么，思考一下当fast为所有的坑里最高的那个，计算完之后对low,fast置，low为最高的，后面的坑不会再求了。因为我们设置的fast高度>=low高度时再求。

        所以正向遍历也就截止到最高处。这里特别注意最高处有等高的情况。

        那么我们进行反向遍历，low为最后一个位置，流程是一样的。得到最高处后面的坑位。如果最高处是等高的话，想一下，会重复计算的。因此我们反向遍历的时候，fast指针要截止到正向遍历时最高等高情况的最后一个位置tag。以防重复计算。

class Solution {public int trap(int[] height) {int reduce_mid = 0;int res = 0;// 从前往后,包含等高情况int low = 0;int fast = low + 1;int tag = 0;while (fast < height.length) {if (height[fast] < height[low]) {reduce_mid += height[fast];fast++;} else {// >=res = res + (fast - low - 1) * height[low] - reduce_mid;reduce_mid = 0;// 标记tag = fast;low = fast;fast = low + 1;}}// 从后往前，遇到等高情况跳过// 置零！！reduce_mid = 0; low = height.length - 1;fast = low - 1;while(fast >= tag ){if(height[fast] < height[low]){reduce_mid += height[fast];fast--;}   else {res = res + (low - fast - 1) * height[low] - reduce_mid;reduce_mid = 0;low = fast;fast = low - 1;}}return res;}
}