Leetcode刷题记录02——双指针

本系列为笔者的 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; } };

作者：力扣官方题解 链接： leetcode /problems/move-zeroes/solutions/489622/yi-dong-ling-by-leetcode-solution/ 来源：力扣（LeetCode）