【Weekly Algorithm】算法周记之《代码随想录》单调栈和图论（一）
学习小结
本周跟随《代码随想录》学习关于单调栈的知识，同时开启图论。
单调栈通过保持一个栈从栈顶到栈底的递增或是递减序列，来解决找一个元素左/右的“第一个”更大/更小元素。
图论则是初窥dfs的门路，虽然道理一年前早在算法课学过考过，但现在也得复习才能捡回来。
单调栈
每日温度
题意：给一个整数数组，求每个数字右侧比该数字更大的间距
方法：暴力解法就是O(n^2)的遍历。更高效率的方法是使用单调栈，所谓的单调栈就是从栈顶到栈底递增或递减的，如此排列，就能方便找任意元素的左右第一个更大更小的元素。
比如本题是找右边更大的，那么遍历数组时，遇到更小或相等的元素就直接入栈，而遇到更大的元素就弹栈，直到触底或碰到大元素再入栈，其中弹栈的元素就能记录本元素的下标与当时元素下标之差。
参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> result(temperatures.size(), 0);
stack<int> st;
st.push(0);
for (int i = 1; i < temperatures.size(); i++) {
if (temperatures[i] <= temperatures[st.top()]) {
st.push(i);
}
else {
while(!st.empty() && temperatures[i] > temperatures[st.top()]) {
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
};下一个更大的元素I
题意：给两个整数数组，找一个数组在另一个数组对应元素的下一个更大元素的集合。
方法：用哈希建立两个数组元素和下标的对应，单调栈则实现元素的下一个更大的元素。
参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
// 按照代码随想录思路，用哈希表构建两数组之间的映射，然后得出nums2单调栈，由此就得到了结果
unordered_map<int, int> umap; // 从nums2数字到nums1对应数字下标的映射
for (int i = 0; i < nums1.size(); i++) {
umap[nums1[i]] = i;
}
// 求nums2单调栈
// vector<int> next(nums2.size(), -1);
stack<int> st;
vector<int> result(nums1.size(), -1);
if (result.size() == 1) return result;
st.push(0);
for(int i = 1; i < nums2.size(); i++) {
if (nums2[i] <= nums2[st.top()]) {
st.push(i);
}
else {
while(!st.empty() && nums2[i] > nums2[st.top()]) {
// next[st.top()] = i - st.top();
if (umap.count(nums2[st.top()]) > 0) {
result[umap[nums2[st.top()]]] = nums2[i];
}
st.pop();
}
st.push(i);
}
}
return result;
}
};下一个更大的元素II
题意：和[[下一个更大的元素I]]相似，但是下一个更大元素要看循环数组。
方法：解决循环以往就有把数组循环乘二的情况，但是这种处理方式对于空间稍显浪费，所以还有一种方式，就是循环时当作两倍的情况。
参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
stack<int> st;
st.push(0);
for (int i = 0; i < nums.size()*2; i++) {
if (nums[i % nums.size()] <= nums[st.top()]) {
st.push(i % nums.size());
}
else {
while(!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
result[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
}
return result;
}
};接雨水
题意，给一个高度数组，每个数字代表柱子高度，求下完雨后，柱子之间积水量
方法，暴力解法，按行或列求，以按列为例，对每一列求其左右最高柱子高度，取最小值，与该列高度差为该列水量。优化方法是用双指针，分别从两侧向另一侧遍历，求每个柱子一侧方向的最高柱子，这样就避免了暴力方法中重复求两侧柱子高度的浪费；
重点在于单调栈方法，按行求，单调栈保持递增（栈顶到栈底），具体处理方法写在注释中
参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int sum = 0;
st.push(0);
for (int i = 1; i < height.size(); i++) {
// 三种情况
// 第一种，后续柱子高度低于栈顶，则直接入栈
if (height[i] < height[st.top()]) {
st.push(i);
}
// 第二种，后续柱子高度与栈顶一致，则更新栈顶，坐标保留靠右的
// 因为如果右侧有凹陷，计算积水的左侧左边起始是从靠右的柱子开始计算
else if (height[i] == height[st.top()]) {
st.pop();
st.push(i);
}
// 第三种，后续柱子比栈顶高，开始计算积水
// 总得来说，就是计算i，栈顶和栈顶前一个柱子三个柱子之间的积水
// 高度上，取左右两柱子的最小值，宽度上，就计算左右柱子的间隔就好
// 上述步骤循环，直至新柱子小于栈顶位置再入栈（或者栈空）
// 计算完成后，左侧柱子在栈顶位置，还有计算价值，毕竟说不定后续用作底部柱子使用
else {
while(!st.empty() && height[i] > height[st.top()]) {
int bottom = height[st.top()];
st.pop();
if (!st.empty()) { // 防止遇到没有左侧柱子的情况
int h = min(height[i], height[st.top()]) - bottom;
int w = i - st.top() - 1;
sum += h*w;
}
}
st.push(i);
}
}
return sum;
}
};柱状图中最大的矩形
题意：给一个柱状图（数组表示）求其中最大矩形面积
方法：实际上与[[接雨水]]相似，但是单调栈方向相反，[[接雨水]]栈顶到栈底递增，如此就能对于每个柱子找到旁边更大的柱子；这里则是递减，找到更小的柱子，以两侧小柱子为下标区间，乘以基准柱子高度，就是一块矩形面积
参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.insert(heights.begin(), 0);
heights.push_back(0);
stack<int> st;// 存储下标
int result = 0;
st.push(0);
for (int i = 1; i < heights.size(); i++) {
if (heights[st.top()] < heights[i]) {
st.push(i);
}
else if (heights[st.top()] == heights[i]) {
st.pop();
st.push(i);
}
else {
while(!st.empty() && heights[st.top()] > heights[i]) {
int mid = st.top();
st.pop();
if (!st.empty()) {
int left = st.top();
int right = i;
int w = right - left - 1;
int h = heights[mid];
result = max(result, h * w);
}
}
st.push(i);
}
}
return result;
}
};
图论
所有可达路径
- 代码随想录
- 98. 所有可达路径
- 题意：给一个无环有向图，要求一个初次节点到末尾节点的所有路径
- 方法：dfs，重点在于具体的实现方法，注意邻接矩阵的vector长度，是n+1，因为题目的编号是1-n。还有题目的输出示例格式要求。
- 参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void dfs(vector<vector<int>> &g, int vis, int end) {
if (vis == end) {
result.push_back(path);
// cout << "path:" << endl;;
// for (int i = 0; i < path.size(); i++) {
// cout << path[i] << " ";
// }
// cout << endl;
return;
}
for (int i = 1; i <= end; i++) {
if (g[vis][i] == 1) {
path.push_back(i);
dfs(g, i, end);
path.pop_back();
}
}
}
int main() {
int n, m;
cin >> n >> m;
// 用邻接矩阵来存储看看
vector<vector<int>> g(n+1, vector<int>(n+1, 0));
for (int i = 0; i < m; i++) {
int s, t;
cin >> s >> t;
g[s][t] = 1;
}
path.push_back(1);
dfs(g, 1, n);
if (result.size() == 0) {
cout << "-1" << endl;
}
for (int i = 0; i < result.size(); i++) {
vector<int> &t = result[i];
for (int j = 0; j < t.size()-1; j++) {
cout << t[j] << " ";
}
cout << t[t.size()-1] << endl;
}
return 0;
} 岛屿数量深搜版
- 代码随想录
- 99. 岛屿数量
- 题意：给一个二维数组，数组中横纵相连视为一个岛，求岛屿数量
- 方法：dfs，模板题，重点在于注意数组的存储
- 参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
void dfs(const vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y) {
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
visited[nextx][nexty] = true;
dfs(grid, visited, nextx, nexty);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
vector<vector<bool>> visited(n, vector<bool>(m, false));
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
visited[i][j] = true;
result++;
dfs(grid, visited, i, j);
}
}
}
cout << result << endl;
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！
相关推荐
2024-11-17
【Weekly Algorithm】算法周记之《代码随想录》动态规划（一）
学习小结本周跟随《代码随想录》开始学习动态规划的相关题目，从基础的斐波那契数到爬楼梯，再到 01 背包问题，慢慢熟悉动态规划的五步法。《代码随想录》还提醒，调试重点是检查递推公式是否举例，检查打印 dp 数组是否和自己设想一致。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 此外除了寻常的二维数组动态规划，也尝试做滚动数组的练习。 动态规划 斐波那契数 题意，给一个数字 n，求斐波那契数中的第 n 个数 方法，虽然就算不看代码随想录也能轻易写出，但简单题的重点在于熟悉套路方法，下面按五步分析 确定 dp 数组及其下标含义，这里的 dp[i] 代表斐波那契数中的第 i 个数 确认递推公式，题目给出 dp[i]=dp[i-1]+dp[i-2] dp 数组初始化，题目也给出dp[0]=0;dp[1]=1; 确定遍历顺序，从递推公式可见，就是从前向后（0-n）遍历 举例推导 dp 公式，0 1 1 2 3 5 8 13 21 …… 陆爻齐的解 1234567891011121314class...
2024-11-24
【Weekly Algorithm】算法周记之《代码随想录》动态规划（二）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，由于期末月的到来，以及题目难度的增加，暂且将动态规划的学习进度放慢一点。下面继续巩固五步法。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 只能感叹，这动态规划真是一百道题才入门啊。 动态规划 分割等和子集 代码随想录 416. 分割等和子集 - 力扣（LeetCode） 题意，给一个数组，返回判断该数组是否能平分为和相等的两部分 方法，直觉上，可以用回溯遍历树，找到那个子节点，但复杂度太高。本题其实就是 01 背包的应用，nums[i] 本身，是物品，重量，以及价值。数组能否平分和的本质，就是平分和的大小的背包能否被刚好装满，也就是下标与值相等。 参考代码随想录思路的代码 1234567891011121314151617class Solution {public: bool canPartition(vector<int>& nums) { int sum =...
2024-12-01
【Weekly Algorithm】算法周记之《代码随想录》动态规划（三）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，主要是完全背包的入门，体会其与 01 背包的不同与关联。 下周两门考试，教务脑子真是进了水，搞这么紧干嘛。 动态规划 完全背包理论 代码随想录 52. 携带研究材料（第七期模拟笔试） 题目，与 [[01背包理论]]的差别在于一个物品可携带多次，求最大价值 方法， dp[j]，在遍历物品时，截止到空间为 j，可装入的最大价值 递推公式，dp[j]=max(dp[j],dp[j-weigh[i]]+val[i]) 初始化，全 0 遍历方向，重点，这是与 01 背包区别最大的地方，01 的滚动数组强调倒序遍历就是为了避免重复，在完全背包中，恰恰需要正序从而利用重复装入物品 举例，…… 参考代码随想录思路的解法 12345678910111213141516171819202122232425262728#include <iostream>#include <vector>using namespace std;int main() { int n, v; ...
2024-12-15
【Weekly Algorithm】算法周记之《代码随想录》动态规划（五）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学会了完全背包的应用，多重背包的理论，打劫打家劫舍问题，和股票买卖问题的入门版。认识到了所存储的状态并不只有 整数 这一种形式，还能有多个整数并成的 vector 作为状态使用。 不得不说，动态规划十分的灵活，一百道题入门还不是说说而已啊。 动态规划 完全平方数 代码随想录 279. 完全平方数 - 力扣（LeetCode） 题意，给一个整数 n，求其被完全平方数组成的最小个数。 方法，就是[[零钱兑换II]]的变体，给的零钱变成了自己找小于 n 的完全平方数，背包容量为 n dp[j] 含义为 在背包容量为 j 的情况下，完全平方数的最小组合 递推公式，dp[i]=min(dp[i],dp[i-j*j]+1)，也就是要么保持不变，要么就在已有的组合上加一 初始化，dp[0]=0,这是为了递推公式才这么初始化，也能理解，完全平方数不算...
2025-01-12
【Weekly Algorithm】算法周记之《代码随想录》动态规划（六）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习完买卖股票相关内容，并初步探索子序列的部分。 买卖股票的题有明显的状态转换，但子序列就没那么明显。 动态规划 买卖股票的最佳时机II 代码随想录 122. 买卖股票的最佳时机 II - 力扣（LeetCode） 题意，在[[买卖股票的最佳时机]]的基础上，要求可以多次购买股票，但同一时段只能持有一支股票，也就是再卖出上一支股票前，不允许购入下一支股票。 方法，与[[买卖股票的最佳时机]]的差别，在于考虑购入当前股票时，是在上一支股票考虑购入和卖出的两个情况中取最大，并非直接取历史最便宜股票和当前股票对比。 参考代码随想录思路解法 123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { // dp[i][0] 考虑第i支股票时，考虑买入的情况；dp[i][1] 考虑第i支股票时，卖出的情况 int len =...
2024-12-08
【Weekly Algorithm】算法周记之《代码随想录》动态规划（四）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，不过周五和周日两门考试太重了，浅做两题，接下来非考试周就继续至少一天一道罢。 本周两道题是完全背包求排列数的应用题和完全背包求 组合/排列 的最小组合数，要记得组合与排列的区别在于背包空间和物品的遍历先后顺序，先遍历物品就不会出现物品乱序填背包的情况，所以是求组合数；而先遍历背包空间，使得同一个空间能有相同物品按不同顺序摆放，则是求排列数。 动态规划 爬楼梯（进阶版） 代码随想录 57. 爬楼梯（第八期模拟笔试） 题意，给 n 个台阶，和一起最多能迈 m 个台阶，问有多少不同方法可爬顶端 方法，由于同一步子可迈多次，故为完全背包问题，而且求的是排列数，与[[组合总和IV]]类似 陆爻齐的解法 123456789101112131415161718192021222324#include <iostream>#include <vector>using namespace std;int main() { int n, m; while(cin...
系列文章