目录
🎂移动零
🌙盛最多水的容器
🌼三数之和
🌼接雨水
前缀和 + 辅助数组
双指针
单调栈
🎂移动零
283. 移动零 - 力扣（LeetCode）
关于swap
#include <iostream> #include <vector> #include <algorithm>int main() {std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7};// 交换 vec 中第 1 个和第 7 个元素std::swap(vec[0], vec[6]);// 输出交换后的结果for (const auto &num : vec) {std::cout << num << " ";}std::cout << std::endl;return 0; }7 2 3 4 5 6 1
思路
i = 0, j = 0
为了保证 0 都在末尾，且顺序不变
i 指向 0 && j 指向 非0 元素时
交换两者（交换后，nums[x] <= i 都是非0元素； i < nums[x] <= j，都是 0）
坑
力扣核心代码模式，很容易越界，所以vector遍历时，要注意数组下标的问题
AC 代码
O(n)
class Solution {
public:void moveZeroes(vector<int>& nums) {int i = 0, j = 0, n = nums.size();while (j < n && i < n) {if (!nums[i] && nums[j]) swap(nums[i], nums[j]);if (nums[i] != 0) i++; // 索引自增放后面，防止越界j++;}}
};🌙盛最多水的容器
11. 盛最多水的容器 - 力扣（LeetCode）
i = 0, j = n - 1
ans = 距离 * 短板长度
所以，移动长板，距离变小，短板长度不可能变大，ans↓
只能移动短板
O(n)
class Solution {
public:int maxArea(vector<int>& height) {int ans = 0, n = height.size();int i = 0, j = n - 1;while (i < j) {int Min = min(height[i], height[j]); // 短板长度ans = max(ans, Min * (j - i));if (height[i] <= height[j]) i++;else j--;}return ans;}
};🌼三数之和
15. 三数之和 - 力扣（LeetCode）
思路
外层 for 遍历 i
内层 l, r 双指针
if( + + == 0) 此时 l 和 r 都需要移动
否则，根据 > 0 或 < 0
只移动一个即可
坑
关于去除重复解
1) if (i > 0 && nums[i] == nums[i - 1])continue;2) while (l < r && nums[l] == nums[l + 1])l++; // 重复解 while (l < r && nums[r] == nums[r - 1])r--; // 重复解1) 去掉下标 i 的重复解
2) 去掉下标 l, r 的重复解
AC 代码
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {if (nums.size() < 3) return {}; // 返回空数组vector<vector<int> > ans;sort(nums.begin(), nums.end()); // 排序int n = nums.size();for (int i = 0; i < n - 2; ++i) { // i l rif (nums[i] > 0) return ans; // 直接返回已有答案if (i > 0 && nums[i] == nums[i - 1])continue; // 去除重复解int l = i + 1, r = n - 1;while (l < r) { // 双指针循环判断if (nums[i] + nums[l] + nums[r] == 0) {ans.push_back({nums[i], nums[l], nums[r]});while (l < r && nums[l] == nums[l + 1])l++; // 重复解while (l < r && nums[r] == nums[r - 1])r--; // 重复解l++, r--; // 上面while结束后，还需要再移动一次}else if (nums[i] + nums[l] + nums[r] > 0)r--;elsel++;}}return ans;}
};🌼接雨水
42. 接雨水 - 力扣（LeetCode）
前缀和 + 辅助数组
辅助数组 l[] 和 r[]
思路
每个柱子能盛水的高度，取决于左边最高和右边最高的柱子的短板
具体就是，min(l[i], r[i]) - h[i]
ans[] 可以省略，直接 res += ...
O(n) * 3
class Solution {
public:int trap(vector<int>& h) {int n = h.size();// ans[] 某一根柱子上的雨水vector<int> ans(n), l(n), r(n); // l[] 左边开始最高点, r[] 右边开始最高点l[0] = h[0], r[n - 1] = h[n - 1]; // 这里的赋值，需要以上面的分配空间为前提for (int i = 1; i < n; ++i) l[i] = max(l[i - 1], h[i]); // 上一个l[]或当前h[] 取最大值for (int i = n - 2; i >= 0; --i)r[i] = max(r[i + 1], h[i]);// 对比 h[] 和 l[] / r[] 得到每个柱子接的雨水int res = 0;for (int i = 1; i < n - 1; ++i) // i==0 或 i==n-1，肯定没有雨水if (h[i] < l[i] && h[i] < r[i])res += min(l[i], r[i]) - h[i];return res;}
};双指针
在 前缀和 思路的基础上，用两个指针 left, right 和两个变量 l_max, r_max ，代替两个辅助数组
优化空间复杂度 O(n) --> O(1)
补充解释
前缀和，是顺序遍历所有柱子
而双指针，是两个指针 left(顺序) 和 right(逆序)，双向同时向中间遍历
取较小那边的 max 值，用那边的 max 值，减去那边当前柱子的高度的 h[]
为什么要选 较小 那边的来计算呢？（关键是 当前 两个字）
因为对于 当前的 left 或者 right 来说，较小那边的，一定是制约当前柱子雨水量的 短板
对照着理解下👈
AC 代码
O(n) * 1
class Solution {
public:int trap(vector<int>& h) {int n = h.size(), res = 0;int l = 0, r = n - 1, l_max = 0, r_max = 0;while (l < r) { l_max = max(h[l], l_max);r_max = max(h[r], r_max);// 注意 += 操作完后，对应一边的指针（l 或 r）要移动res += (l_max < r_max) ? (l_max - h[l++]) : (r_max - h[r--]); // 减去对应一边的柱子}return res;}
};单调栈
简介
单调栈 - OI Wiki (oi-wiki.org)
模拟
单调栈【基础算法精讲 26】_哔哩哔哩_bilibili
思路
42. 接雨水 - 力扣（LeetCode）
力扣官方视频 -- 4'56开始看，13'56结束（9分钟）
关于代码中 st.pop() 以及 distance(积水宽度) 的计算👇 结合图理解
实际就是对单调栈的模拟，结合 += ( min(h1, h2) - h ) * 宽，即，(短板 - 当前) * 宽度
过程
1）单调递减栈，储存可能形成 “低洼处” 的柱子
2）遇到更低的柱子，就插入 索引
3）遇到更高的柱子，意味着和前面 更低的，形成了低洼，就进入 内层 while 循环计算积水
4）被弹出的索引 top，h[top] 作为被积水的柱子高度，弹出栈顶后的新栈顶 left，作为 左端点
5）右端点即 当前 for 循环的 i， i - left - 1 即 积水宽度
6）高度取 当前高度 h[i] 和 左端点高度 h[left] 的 较小值
7）积水高度即，min( h[i], h[left] ) - h[top]
8）接着用积水 高度 * 宽度，即得到 += 的积水
9）while ( 栈非空 && 当前高度 h[i] > 栈顶高度 h[st.top()] ) ，重复 (3) ~ (8)
AC 代码
class Solution {
public:int trap(vector<int>& h) {stack<int> st; // 存储下标int n = h.size(), ans = 0;for (int i = 0; i < n; ++i) {while (!st.empty() && h[st.top()] < h[i]) { // 满足 低洼处 条件int top = st.top();st.pop(); // 弹出栈顶if (st.empty()) break; // 左边没有更高的柱子来形成积水int left = st.top();int height = min(h[i], h[left]) - h[top];int width = i - left - 1;ans += height * width;}// stack, queue 都是 push, vector 才是 push_backst.push(i); // 高度降低, 直接插入}return ans;}
};
