LeetCode Hot 100：双指针

283. 移动零

思路 1：遍历

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

思路 2：双指针

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        // left 指向当前已经处理好的序列的尾部
        int left = 0;
        // right 指向待处理序列的头部
        int right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

11. 盛最多水的容器

思路 1：双指针

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;

        int ans = INT_MIN;
        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            ans = max(ans, area);
            if (height[left] < height[right])
                left++;
            else
                right--;
        }

        return ans;
    }
};

15. 三数之和

思路 1：三重循环 + 集合去重（超时）

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        set<vector<int>> set;
        for (int i = 0; i < n - 2; i++)
            for (int j = i + 1; j < n - 1; j++)
                for (int k = j + 1; k < n; k++)
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        vector<int> v = {nums[i], nums[j], nums[k]};
                        sort(v.begin(), v.end());
                        set.insert(v);
                    }

        vector<vector<int>> ans(set.begin(), set.end());
        return ans;
    }
};

思路 2：排序 + 双指针

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        if (n < 3)
            return {};

        sort(nums.begin(), nums.end());
        set<vector<int>> set;
        for (int i = 0; i < n; i++) {
            int target = -nums[i];
            int left = i + 1, right = n - 1;
            while (left < right) {
                if (nums[left] + nums[right] > target)
                    right--;
                else if (nums[left] + nums[right] < target)
                    left++;
                else {
                    vector<int> v = {nums[i], nums[left], nums[right]};
                    set.insert(v);
                    left++;
                    right--;
                }
            }
        }
        vector<vector<int>> ans(set.begin(), set.end());
        return ans;
    }
};

42. 接雨水

思路 1：前后缀分解

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();

        vector<int> preMax(n);
        for (int i = 0; i < n; i++)
        {
            if (i == 0)
                preMax[i] = height[i];
            else
                preMax[i] = max(preMax[i - 1], height[i]);
        }

        vector<int> sufMax(n);
        sufMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--)
            sufMax[i] = max(sufMax[i + 1], height[i]);
        
        int water = 0;
        for (int i = 0; i < n; i++)
            water += min(preMax[i], sufMax[i]) - height[i];

        return water;
    }
};

思路 2：相向双指针

// 相向双指针

class Solution
{
public:
    int trap(vector<int> &height)
    {
        int n = height.size();
        int left = 0, right = n - 1;
        // pre_max 表示前缀最大值，suf_max 表示后缀最大值
        int pre_max = 0, suf_max = 0;
        int sum = 0;

        while (left < right)
        {
            // 更新前后缀最大值
            pre_max = max(pre_max, height[left]);
            suf_max = max(suf_max, height[right]);
            if (pre_max < suf_max)
            {
                sum += pre_max - height[left];
                left++;
            }
            else
            {
                sum += suf_max - height[right];
                right--;
            }
        }

        return sum;
    }
};

思路 3：单调栈

// 单调栈

class Solution
{
public:
    int trap(vector<int> &height)
    {
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < height.size(); i++)
        {
            while (!st.empty() && height[i] >= height[st.top()])
            {
                int bottom_h = height[st.top()];
                st.pop();
                if (st.empty())
                    break;
                int left = st.top();
                // 面积的高和宽
                int dh = min(height[left], height[i]) - bottom_h;
                int dw = i - left - 1;
                ans += dh * dw;
            }
            st.push(i);
        }
        return ans;
    }
};