当前位置：首页 > article >正文

Leetcode 刷题记录 02 —— 双指针

article 2025/3/5 2:24:28

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答。

01 移动零

02 盛最多水的容器

03 三数之和

04 接雨水

01 移动零

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

02 盛最多水的容器

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while(l < r){
            int area = min(height[l], height[r])*(r - l); //计算当前水量
            ans = max(ans, area);

            if(height[l] < height[r]) ++l; //移动挡板
            else --r;
        }
        return ans;
    }
};

03 三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //排序
        sort(nums.begin(), nums.end());

        vector<vector<int>> ans;
        int n = nums.size();
        for(int first = 0; first < (n - 2); ++first){ //1 first < (n - 2)
            if(first > 0 && nums[first] == nums[first - 1]) continue;
		   
            //双指针
            int third = n - 1;
            int target = -nums[first];
            for(int second = (first + 1); second < (n - 1); ++second){ //2 second < (n - 1)
                if(second > (first + 1) && nums[second] == nums[second - 1]) continue;

                while(second < third && nums[second] + nums[third] > target) --third;
                if(second == third) break;
                if(nums[second] + nums[third] == target){
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

04 接雨水

class Solution {
public:
    int trap(vector<int>& height) {
        
    }
};

方法一：哈希数组

建立两个哈希数组，leftMax(n) 和 rightMax(n)
leftMax[i] 用来存储 i 左边的最大柱子
rightMax[i] 用来存储 i 右边的最大柱子
i 的储水值为 min(leftMax[i], rightMax[i]) - height[i]
注：if(n == 0) return 0;

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

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

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

        int ans = 0;
        for(int i = 0; i < n; ++i){
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

方法二：单调栈

建立一个单调栈 stk，用来存储单调不增长柱子序列
遇到高个柱子，秒掉 top，增加一层雨水
一层雨水体积为 (i - left - 1) * (min(height[left], height[i]) - height[top])
注：if(stk.empty()) break;

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

        for(int i=0; i<n; ++i){
            while(!stk.empty() && height[i] > height[stk.top()]){
                int top = stk.top();
                stk.pop();
                if(stk.empty()) break;

                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currHeight * currWidth;
            }
            stk.push(i);
        }
        return ans;
    }
};

方法三：双指针

建立双指针 left 和 right，用来存储左边最大柱子和右边最大柱子
左边柱子低，则移动 left ，添加一列雨水
右边柱子低，则移动 right ，添加一列雨水
一列雨水体积为 leftMax - height[left] 或 rightMax - height[right]

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int ans = 0;
        int left = 0, right = n - 1; //双指针
        int leftMax = 0, rightMax = 0;
        
        while(left < right){
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if(leftMax < rightMax){
                ans += leftMax - height[left];
                ++left;
            }else{
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};