双指针法：通过两个指针在一个for循环下完成两个for循环的工作，一般是将O(n^2)的时间复杂度，降为O(n)

283. 移动零✅

简单模拟 不改变数组内元素的相对位置 复杂度O(n)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        for(int fast = 0; fast < nums.size(); fast++) {
            if(nums[fast]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        for(int i = slow; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

---

11. 盛最多水的容器 ❌

如何做到指针的每一次移动都能排除掉一根柱子

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int front = 0;
        int back = height.size() - 1;
        while(front < back) {
            int area = ((back-front)*(min(height[back], height[front])));
            res = max(res, area);
            if(height[front] <= height[back]) { //思考为什么可以淘汰
                front++;
            } else {
                back--;
            }
        }
         
        return res;
    }
};

题解：https://leetcode.cn/problems/container-with-most-water/solutions/94102/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu

---

15. 三数之和❌

哈希or双指针？

去重噩梦

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        ranges::sort(nums);
        //假定a = nums[i], b = nums[left], c = nums[right]
        for(int i = 0; i < nums.size() - 2; i++) {
            if(nums[i] > 0) return res; //如果a就已经大于0了，那么不管是这个小循环
            //还是之后的所有循环都不可能再有满足条件的组合了
            if(i > 0 && nums[i-1] == nums[i]) continue; //对a去重
            int left = i + 1;
            int right = nums.size() - 1;
            while(left < right) {
                if(nums[i] + nums[left] + nums[right] > 0) right--;
                else if(nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    res.push_back({nums[i], nums[left], nums[right]});
                    while(left < right && nums[left] == nums[left+1]) left++; //对b去重
                    while(left < right && nums[right] == nums[right-1]) right--; //对c去重 
                    left++;
                    right--;
                }
            }

        }

        return res;
    }
};

ps：为什么1. 两数之和不能使用双指针法？

因为两数之和要求返回的是索引下标， 而双指针法一定要排序，一旦排序之后原数组的索引就被改变了

---

42. 接雨水❌

Solution1：双指针 (按列计算)

每一列雨水的高度取决于，该列左侧最高的柱子和右侧最高的柱子中较矮的那个柱子的高度 – 自身高度

Solution2：单调栈 (按行计算)

栈底到栈头元素递减，因为一旦要添加的柱子高度大于栈头元素，说明出现凹槽了

此时，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子

class Solution1 {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int len = height.size();
        //记录当前列的左右两边的最高列
        vector<int> lmax(len);
        vector<int> rmax(len);
        
        lmax[0] = height[0];
        for(int i = 1; i < len; i++) {
            lmax[i] = max(lmax[i-1], height[i]);
        }

        rmax[len - 1] = height[len - 1];
        for(int i = len - 2; i >= 0; i--) {
            rmax[i] = max(rmax[i+1], height[i]);
        }

        for(int i = 0; i < height.size(); i++) {
            int x = min(lmax[i], rmax[i]) - height[i]; //第一列和最后一列的x算出来是0           
            if(x > 0) res += x; //是正数才说明能接住雨水，负数的情况比如最高列
        }

        return res;
    }
};

class Solution2 {
public:
    int trap(vector<int>& height) {
        stack<int> sk; //存下标
        int res = 0;
        sk.push(0);

        for(int i = 1; i < height.size(); i++) {
            while(!sk.empty() && height[i] > height[sk.top()]) { //出现凹槽
                int mid = height[sk.top()]; //凹槽中间柱子高度
                sk.pop();
                if(!sk.empty()) {
                    int left = height[sk.top()]; //凹槽左边柱子高度
                    int right = height[i]; //凹槽右边柱子高度
                    int h = min(left, right) - mid;
                    int w = i - sk.top() - 1;
                    res += h * w; //高×宽
                }
            }
            sk.push(i);
        }

        return res;
    }
};