「LeetCode Top100」之双指针

2024-08-10 20:48 由云雀AC了一整天发表于 #其他

283. 移动零

题目链接：https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
题目难度：简单
标签：数组、双指针
题目状态：AC

思路：

两个指针，i 用来找 0，j 用来找非0。当nums[i] == 0 && nums[j] != 0时，将两者交换。

代码：

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

11. 盛最多水的容器

题目链接：https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked
题目难度：中等
标签：贪心、数组、双指针
题目状态：ChatGPT协助

思路：

前后指针，依次遍历，直到前后指针交叉了，每次遍历的时候记录当前遍历得到的最大容量。

代码：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max = 0;
        int left = 0;
        int right = height.size() - 1;
        while(left < right) {
            if(height[left] < height[right]) {
                max = std::max(max, (right - left) * height[left]);
                left++;
            } else {
                max = std::max(max, (right - left) * height[right]);
                right--;
            }
        }
        return max;
    }
};

15. 三数之和

题目链接：https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
题目难度：中等
标签：数组、双指针、排序
题目状态：AC

思路：

首先对数组进行排序，然后用一个指针来固定第一个元素，之后使用双指针来遍历数组后面的其他元素，寻找三数之和为目标值的三个数，具体细节看代码。

代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] > 0 ) break;
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.size() - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0) right--;
                else if(sum < 0) left++;
                else {
                    res.push_back({nums[i], nums[left], nums[right]});
                    while(right > left && nums[right] == nums[right - 1]) right--;
                    while(right > left && nums[left] == nums[left + 1]) left++; 
                    left++;
                    right--;
                } 
            }
        }
        return res;
    }
};

42. 接雨水

题目链接：https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
题目难度：困难
标签：栈、数组、双指针、动态规划、单调栈
题目状态：看题解

题解中给了三种思路，一种动态规划、一种单调栈，一种双指针，个人认为动态规划的方式更好理解，其次是双指针方法，最难是单调栈。

思路一：动态规划

这道题记录了两个动规数组leftMax[i]、rightMax[i]，leftMax[i]表示当前位置i的左边最大的值是多少，rightMax[i]表示当前位置i的右边最大的值是多少。当全部记录下来之后，再次遍历数组，判断位置i记录的leftMax和rightMax的最小值，将这个最小值减去i的值，这个值就是积攒的雨水，下图（来自LeetCode官方题解）更好理解：

代码一：

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; ++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;
    }
};

思路二：单调栈

初始化变量：
- ans：用于存储总的雨水量。
- stk：一个栈，用于存储柱子的索引。
- n：高度数组的大小。
遍历高度数组：
- 对于每个柱子高度height[i]：
  - 检查栈顶元素：如果当前高度大于栈顶的高度，说明可以形成一个“洼地”。
  - 计算雨水量：
    - 弹出栈顶元素，作为当前洼地的底部。
    - 如果栈为空，说明没有左边界，无法形成洼地，继续下一个。
    - 否则，计算当前洼地的宽度 currWidth 和高度 currHeight：
    - currWidth 是当前索引 i 与新的栈顶 left 之间的距离减一。
    - currHeight 是形成洼地的左右边界的最小高度减去底部高度。
  - 将洼地的雨水量加到 ans 中。
将当前索引压入栈：
- 继续处理下一个柱子。
返回结果：
- 最终返回累计的雨水量 ans。

代码二：

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        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 += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }
};

思路三：双指针

初始化变量：
- ans：用于存储总的雨水量。
- left 和 right：分别指向数组的左右两端。
- leftMax 和 rightMax：分别记录从左到右和从右到左的最大高度。
双指针遍历：
- 当 left 小于 right 时，进行以下操作：
  - 更新 leftMax 和 rightMax，分别为当前指针位置的最大高度。
  - 比较 height[left] 和 height[right]：
  - 如果 height[left] 小于 height[right]：
    - 计算左边可以储水的量 leftMax - height[left]，并加到 ans。
    - 移动左指针 left 向右。
  - 否则：
    - 计算右边可以储水的量 rightMax - height[right]，并加到 ans。
    - 移动右指针 right 向左。
返回结果：
- 最终返回累计的雨水量 ans。

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