Leetcode 刷题记录 02 —

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