力扣hot100——双指针

283. 移动零

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

 双指针，一个指针指向要修改的位置，另一个指针遍历数组

11. 盛最多水的容器

class Solution {
public:int maxArea(vector<int>& a) {int l = 0, r = a.size() - 1;int ans = 0;while (l < r) {ans = max(ans, (r - l) * min(a[l], a[r]));if (a[l] < a[r]) l++;else r--;}return ans;}
};

15. 三数之和

class Solution {
public:struct node {int x, y, z;bool operator<(const node& t) const {if (x != t.x)return x < t.x;if (y != t.y)return y < t.y;if (z != t.z)return z < t.z;return false;}};vector<vector<int>> threeSum(vector<int>& a) {sort(a.begin(), a.end());int n = a.size();set<node> s;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {int t = a[i] + a[j];t *= -1;int l = i + 1, r = j - 1;while (l < r) {int mid = (l + r + 1) / 2;if (a[mid] <= t) l = mid;else r = mid - 1;}if (l > i && l < j && a[l] == t)s.insert({a[i], a[l], a[j]});}}vector<vector<int>> ans;for (auto [x, y, z]: s) {ans.push_back({x, y, z});}return ans;}
};

哈希，模拟

42. 接雨水

class Solution {
public:int trap(vector<int>& height) {vector<int> a;a.push_back(0);int n = height.size();vector<int> l(n + 10, 0);vector<int> r(n + 10, 0);for (auto x : height)a.push_back(x);int ans = 0;for (int i = 1; i <= n; i++) {l[i] = r[i] = a[i];}stack<int> stk;for (int i = 1; i <= n; i++) {while (stk.size() && a[i] > a[stk.top()])stk.pop();if (stk.size()) {l[i] = l[stk.top()];}stk.push(i);}while (stk.size())stk.pop();for (int i = n; i >= 1; i--) {while (stk.size() && a[i] > a[stk.top()])stk.pop();if (stk.size()) {r[i] = r[stk.top()];}stk.push(i);}for (int i = 1; i <= n; i++) {int t = min(l[i], r[i]);if (t > a[i]) ans += t - a[i];}// return l[6];return ans;}
};

单调栈，找每根柱子左边第一个比他大的，右边第一个比他大的，那么这根柱子的贡献就是二者的最小值-它自己