本仓库用于记录在刷题过程中总结的一些技巧和经验，方便日后复习和参考。
map:- 适用于
键值对中键为非整数类型的情况，如字符串、浮点数等。 - 键为
整数时,但分布稀疏,范围较大时也适用。 - 实现基于
红黑树，查询、插入、删除的时间复杂度为O(log n)。
- 适用于
unorder_map:- 适用于
键为整数类型，且范围较大但分布较密集`的情况。 - 实现基于
哈希表，查询、插入、删除的时间复杂度为O(1)的平均时间复杂度，但在最坏情况下可能退化为O(n)。
- 适用于
vector(数组):- 适用于
键为整数类型,且范围较小且分布较密集的情况。可以实现O(1)的查询(通过索引直接访问)。
- 适用于
unordered_set：底层使用的哈希表，适用于需要快速判断元素是否存在的场景，平均时间复杂度为O(1)，但在最坏情况下可能退化为O(n)。这个使用于绝大数据范围场景，是数据值域较大但分布稀疏的最优选择。数组：适用于数据值域较小且分布较密集的场景，可以实现O(1)的访问效率。对于数据值域较小且分布较密集的场景，使用数组可以节省空间并提高访问效率。虽然unorder_set也能处理，但这个是对其的空间优化，避免了哈希表的额外空间开销。bitset：适用于需要存储大量布尔值的场景，可以实现O(1)的访问效率，并且节省空间。对于数据值域较小且分布较密集的场景，使用bitset可以进一步节省空间，因为它以位为单位存储数据，相比于数组或哈希表的字节级存储更为紧凑。
- 队列(queue) 是一种先进先出(FIFO)的数据结构，适用于需要按顺序处理元素的场景。时间滑动窗口的问题,这里的固定大小,通过
手动计数维护 - 权重自动排序 将时间先后顺序转化为权重排序：能实现自动排序的有
priority_queue(堆):中间插入和删除时间复杂度为O(log n),理论上和set,map类似,但实际运行时间会更快一些,因为底层实现更简单,没有红黑树那么复杂的旋转操作。但是不支持按值查找(存不存在)、修改和删除操作,只能删除堆顶元素,即不能访问和操作中间元素。set：支持自动排序和按值查找、删除操作,时间复杂度为O(log n),底层实现为红黑树，而且自带去重功能。可以操作中间元素,而且存储时所有元素严格有序map: 支持键值对存储，按键自动排序，时间复杂度为O(log n)，底层实现为红黑树。适用于需要按键排序且需要存储额外信息的场景。可以操作中间元素,而且存储时所有元素严格有序
单点动态修改注意：在第一次查询完后，如果动态单点修改，其实后面很大一部的元素第二次去查询时是没有变化的，只有与被修改点相关的元素才会发生变化，所以可以在每个节点添加统计标记(缓存)，避免重复计算,但单点修改时，需要更新与该节点相关的所有节点的缓存标记。这样可以避免每次查询时不必要的重复计算，提高查询效率。
- 当对半分
0~n下标的问题时，如果为奇数,则i<=(n-1)/2是不包含中间节点,即后半部分比前半部分多一个节点的;i<=n/2则包含中间节点,前面比后面多一个中间节点。
快慢指针用于寻找链表的中间节点时,当为奇数时,慢指针最终指向中间节点;思路：if(head==nullptr) return nullptr; ListNode* slow = head; ListNode* fast = head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } // 当链表长度为奇数时，slow 指向中间节点 // 可以直接通过 if(fast->next != nullptr) 判断链表长度为偶数还是奇数 if(fast->next != nullptr){ // 链表长度为偶数 } else { // 链表长度为奇数，slow 指向中间节点 }
0号节点废了，后面走的时候，每次走的时候fast指针指向的下标都是slow指针的两倍,所以当最后一个节点下标是2n时,则slow指针指向n号节点,即中间节点.
- 痛点：
- 无法高效获取长度，无法根据偏移快速访问元素
- 处理链表时，常常需要使用
哨兵节点(虚拟头节点)来简化边界条件的处理。
- 双(快慢)指针 经常用来解决链表中的无法随机访问的问题。
- 中间节点
- 环形链表:
-
快慢指针：如果有环，只要一直跑，
快指针一定会追上慢指针,即两指针会相遇,但不保证相遇的点是环的入口点,可以使用数学等式推到出位置,看leetcode 142题。-
除了官方数学推理，还可以在相遇时，让一个指针继续走一圈，计算出环的长度
C。然后重头开始,让一个指针多走C步，再让两个指针同时走，最终会在环的入口点相遇。 -
环前面的长度可以直接按照官方解，在相遇后，让一个指针回到头节点，然后两个指针同时走，计算步数，最终会在环的入口点相遇。
-
-
标记：如果节点中数据有范围，可以使用将走过(一般使用在原处
标记或者使用容器(unorder set等)记录并查找判断下来)的节点数据标记为一个特殊值(如INT_MAX),如果再次遇到该值,则说明有环。即走过的路径做标记或者染色。
-
- 倒数第K个节点
四平方和定理是数论中的一个重要定理，指出每个自然数都可以表示为四个整数的平方和。换句话说，对于任何自然数
n，都存在整数a、b、c、d，使得n = a^2 + b^2 + c^2 + d^2。
更强的结论：
- 当
$n = 4^k(8m+7)$ 时，n必须表示为四个整数的平方和。 - 当
$n\neq 4^k(8m+7)$ 时，n可以表示为三个整数的平方和。 - 当
$n = a^2 + b^2$ 且$a$ 和$b$ 不是同时为零时，n可以表示为两个整数的平方和。 - 当
$n$ 是完全平方数时，n可以表示为一个整数的平方和。
class Solution {
public:
// 判断是否为完全平方数
bool isPerfectSquare(int x) {
int y = sqrt(x);
return y * y == x;
}
// 判断是否能表示为 4^k*(8m+7)
bool checkAnswer4(int x) {
while (x % 4 == 0) {
x /= 4;
}
return x % 8 == 7;
}
int numSquares(int n) {
if (isPerfectSquare(n)) {
return 1;
}
if (checkAnswer4(n)) {
return 4;
}
for (int i = 1; i * i <= n; i++) {
int j = n - i * i;
if (isPerfectSquare(j)) {
return 2;
}
}
return 3;
}
};
处理方式分为两种：
- 借用全局(对象普通)变量递归下降到叶子节点时记录路径：在递归函数中传入一个
当前路径参数，表示从根节点到当前节点的路径。当递归到达叶子节点时，将当前路径加入结果集。
- 优点:
- 借助全局变量或者对象的普通变量，可以避免在回溯时对于同一子树回溯时，在父节点及以上的祖宗节点中重复拼接相同的路径,从而提高效率。因为回溯相当于对于相同父节点的每个叶子节点都要一步一步的拼接复制相同路径
- 直接往后面添加元素,避免在头部插入元素的低效问题。
- 借助全局变量或者对象的普通变量，可以避免在回溯时对于同一子树回溯时，在父节点及以上的祖宗节点中重复拼接相同的路径,从而提高效率。因为回溯相当于对于相同父节点的每个叶子节点都要一步一步的拼接复制相同路径
- 缺点：
- 看后面方法的对比
class Solution { private: vector<vector<int>> result_; vector<int> currentPath_; private: void backtrack(TreeNode* node) { if (node == nullptr){ result_.push_back(currentPath_); // 到达叶节点，记录路径 return; } currentPath_.push_back(node->val); // 添加当前节点到路径 backtrack(node->left); // 递归左子树 backtrack(node->right); // 递归右子树 currentPath_.pop_back(); // 回溯，移除当前节点 } }
- 优点:
- 递归回溯记录路径：在
回溯时,将子节点的路径结果返回给父节点,父节点再将自己的值添加到子节点路径的前面,形成完整路径。
- 缺点：
- 这里的返回值返回上一层时编译器可以利用
RVO(返回值优化)来避免在父节点调用栈中重新赋值拷贝子节点返回的路径结果,从而提高效率,所以这里的效率几乎不用考虑。 - 但有一点需要注意的时，这时往往涉及到在
vector的开头插入元素的问题,这时可以使用deque来代替vector,因为deque在头部插入元素的时间复杂度为O(1),而vector在头部插入元素的时间复杂度为O(n)。
- 这里的返回值返回上一层时编译器可以利用
- 优点：
- 这种方法不需要额外的全局变量，代码更简洁，逻辑更清晰。而上面一种涉及到外部变量，使用前必须将涉及到的变量清空,否则会影响结果，可重入性差，副作用大。
- 这个方法对于会出现分支时多次处理相同区域子问题时，可以使用
记忆化来避免重复计算，从而提高效率。而上面一种由于在叶节点时才记录路径，回溯时无法知道尾部区域的子问题的完整返回答案，所以无法使用记忆化来优化。
unordered_map<TreeNode*, vector<vector<int>>> memory; // 记忆化存储子问题结果 vector<vector<int>> path(TreeNode* root){ if(root == nullptr){ return {{}}; // 到达叶节点，返回空路径 } //!!! 优势：可以使用记忆化避免重复计算 if(memory.count(root)) return memory[root]; // 使用记忆化避免重复计算 vector<vector<int>> result; for(auto& subPath : path(root->left)){ subPath.insert(subPath.begin(), root->val); // 在路径前面插入当前节点 result.push_back(subPath); } for(auto& subPath : path(root->right)){ subPath.insert(subPath.begin(), root->val); // 在路径前面插入当前节点 result.push_back(subPath); } memory[root] = result; // 记录结果，避免重复计算 return result; }
- 缺点：
常用技巧：
- 对角线坐标关系：对于一个坐标点
(x, y)，其所在的对角线可以通过x + y或者x - y来唯一确定。即对于同一条对角线上的所有点，它们的x + y或者x - y的值是相同的。 - 存储问题：对于地图问题，如果需要频繁访问某个坐标点的值，可以使用
二维数组或者哈希表来存储地图数据。对于稀疏地图，可以使用哈希表来存储非空坐标点的数据，以节省空间,使用unordered_set可以实现O(1)的访问;对于密集地图，可以使用二维数组来存储数据，以提高访问效率。
讨论：unordered_set,bitset和手动位图- 三者都可以实现
O(1)的访问效率 - 在
非连续的状态信息存储(如坐标点)中,使用unordered_set相当于只要存储需要记住的信息,在信息稀疏的情况下可以节省空间； 而在连续紧凑的状态信息中如(地图，表格等),可以将状态信息压缩到bitset或者手动位图中,相当于一个byte就可以存储8个状态空间，以节省空间和提高访问效率 - 手动操作位图时常用技巧：
设置第i位为1:bitmap |= (1 << i);清除第i位(设置为0):bitmap &= ~(1 << i);检查第i位是否为1:(bitmap & (1 << i)) != 0切换第i位的状态:bitmap ^= (1 << i);最低位的1:bitmap & (-bitmap)清除最低位的1:bitmap & (bitmap - 1)最低为的1的位置:__builtin_ctz(bitmap)(GCC内置函数，返回bitmap中最低位的1的位置，0表示最低位是第0位)
int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2)); // 计算当前行可用的位置 while (availablePositions != 0) { int position = availablePositions & (-availablePositions); // 获取最低位的1，表示一个可用的位置 availablePositions = availablePositions & (availablePositions - 1); // 清除最低位的1，表示这个位置已经被使用 int column = __builtin_ctz(position); // 获取这个位置对应的列索引 }
- 三者都可以实现
- 双指针法：
只判断单个字符串是否为回文串。
bool isPalindrome(const string& s) { int left = 0; int right = s.size() - 1; while (left < right) { if (s[left] != s[right]) { return false; // 字符不相同，非回文串 } left++; right--; } return true; // 所有字符都相同，是回文串 }
- 寻找回文串
回文串有两种情况：
奇数长度回文串和偶数长度回文串，可以分别以每个字符为中心，向两边扩展来寻找回文串。string expandAroundCenter(const string& s, int left, int right) { while (left >= 0 && right < s.size() && s[left] == s[right]) { left--; right++; } return s.substr(left + 1, right - left - 1); // 返回回文串 } string longestPalindrome(string s) { string longest; for (int i = 0; i < s.size(); ++i) { // 奇数长度回文串 string oddPalindrome = expandAroundCenter(s, i, i); if (oddPalindrome.size() > longest.size()) { longest = oddPalindrome; } // 偶数长度回文串 string evenPalindrome = expandAroundCenter(s, i, i + 1); if (evenPalindrome.size() > longest.size()) { longest = evenPalindrome; } } return longest; }
- 动态规划：
对于一个子串的
任意长度子串是否为回文串，可以使用动态规划来预处理。因为如果每次去判断的话，会有大量重复计算，而利用动态规划的话可以充分利用里面已经计算过的子串结果，从而提高效率。例如：aabbaa，当判断abba是否为回文串时，可以利用已经计算过的bb是否为回文串的结果，不用基础用双指针走进bb中间去判断。
思考点：vector<vector<bool>> dp(n, vector<bool>(n, true)); // dp[i][j] 表示子串 s[i..j] 是否为回文串，默认反序也为 true for (int i = n - 2; i >= 0; --i) { // 注这里是从后往前遍历,因为 dp[i][j] 依赖于 dp[i+1][j-1] 和 s[i]==s[j] 遍历顺序是和递推公式相关的，必须保证 dp[i+1][j-1] 已经被计算过 for (int j = i+1; j < n; ++j) { dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]; // 如果为2个字符串，则i+1>j-1,反序了，默认是 true } }
- 动态规划 相当于知道往哪个方向去利用已知信息，然后提前利用这些信息推出所有节点. 本质是利用已知信息，这个已知信息可能就是原来问题的子问题的结果(很大一部分就是原来问题的子问题)，也有一部的已知信息是需要自己设计表示信息的状态的而不是原来的子问题，比如背包问题
- 记忆化 相当于在需要的时候才去判断有没有计算过，然后利用已知信息推出部分节点，不会计算所有节点，只有需要的节点才会被计算。 如果重复计算的点有出现时刻某个顺序趋势的话，可以使用动态规划逆着这个趋势，在要利用已知信息的节点之前就提前计算出这些已知信息，从而避免重复计算。
这里的随便选择k个元素，即$\sum_{k=0}^{n} {C_n^{k}}$组合问题. 即随便选几个元素的问题。思路：
第一个元素可以依次在left~right中选择，然后递归选择下一个元素，即从selectPos+1~right中选择下一个第一个元素的子问题。
这个和将一段连续区间划分为若干段的问题是一样的,即从left~right中选择第一个划分点结尾,然后递归地选择下一个第一个划分点结尾。其中对于相同子问题区域会出现重复搜索,可以使用记忆化来避免重复计算。
-
不可重复选择:
-
2进制模拟，即从0到2^n - 1遍历，每个数的二进制表示对应一个组合，1表示选择该元素，0表示不选择该元素。vector<vector<int>> subsets(vector<int>& nums) { int n = nums.size(); vector<vector<int>> result; for (int i = 0; i < (1 << n); ++i) { // 遍历从 0 到 2^n - 1 vector<int> subset; for (int j = 0; j < n; ++j) { if (i & (1 << j)) { // 检查第 j 位是否为 1 subset.push_back(nums[j]); } } result.push_back(subset); } return result; }
-
递归回溯: 递归可以在当前的选择中再多生出n中不同选择路径。递归中根据是否选择当前元素来实现分支，注意 在选择了的分支递归完之后的回溯阶段记得撤销选择,以便进行下一次选择。
从左到右按照循序判断每个元素选/不选,实现二叉树的分支。// 或者 这种没有剪枝 void backtrack(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) { if (index == nums.size()) { result.push_back(current); // 将当前组合加入结果 return; } // 不选择当前元素 backtrack(nums, index + 1, current, result); // 选择当前元素 current.push_back(nums[index]); backtrack(nums, index + 1, current, result); current.pop_back(); // 撤销选择，回溯 } // 或者 这种有剪枝 index 表示起始下标 void backtrack(vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) { // 如果会出现搜索相同子问题区间，可以添加记忆化避免重复计算，实现剪枝。但这里使用的是 下降过程借用对象普通变量进行存储路径，无法使用记忆化。 if (start > nums.size()){ result.push_back(current); // 将当前组合加入结果 return; } result.push_back(current); // 将当前组合加入结果 for (int i = start; i < nums.size()+1; ++i) { current.push_back(nums[i]); // 选择当前元素 backtrack(nums, i + 1, current, result); // 递归选择下一个元素 current.pop_back(); // 撤销选择，回溯 } }
-
背包问题(动态规划): 这里的记忆化如果访问顺序有一定的先后规律的话,可以使用动态规划来提前计算出所有子问题的结果,从而避免重复计算。 一般都能写出递推关系式.
与树展开联系理解：-
树相当于每一层的节点针对于当前下标元素的选/不选分支,最终的叶子节点会有2^n个,如果遍历到每一个叶子节点，则时间复杂度为O(2^n)。值的注意的是，其实对于每一层来说(即使是最后一层)，每个分叉其实都是一样的操作含义,即选/不选当前元素,那为什么当前层会出现2^k个分叉呢？ 因为虽然对于当前层来说每个分叉的操作含义是一样的,但是由于之前层的分叉已经产生了2^(k-1)个分叉了,即相当于现在重复分叉虽然操作含义一样，但同时记录了之前的选择状态(路径)。即如果不考虑记录之前的状态的话，可以将每一层都压缩到一个分叉,即选/不选当前元素,这样时间复杂度就变成了O(n)了，不用遍历最后一层的每一个叶子节点了。 -
动态规划比如(背包问题)，则dp[i][j]每个i对应于树的每一层,$dp[i][j]=max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])$相当于对于当前层的每个分叉(选/不选当前元素)的结果,即选/不选当前元素的结果。但由于同样希望保存有一定的状态，但又不希望出现太多的状态(分叉),所以使用了一种相对更为紧凑的状态表示方法,即j表示到当前考虑的前i个选择中背包的容量j所能达到的最大价值,它相当于不用记录之前树每一种选/不选的路径O(2^n)，而使用一种压缩的状态表示方法来记录状态,相当于只要记录volume种状态即可O(volume)，特别是层数(物品，可选择对象)增加时，动态规划的优势就会越来越明显了，树的分叉会呈指数级增长，而动态规划的状态数仍然是volume，所以动态规划在处理大规模问题时通常比树更高效。
-
-
注意这里的
动态规划和背包问题区别：-
背包问题只是动态规划中的一种，动态规划本质上是利用重叠子问题把需要的信息提前计算出来，避免重复计算,如果不知道更新顺序的话，就会退化到记忆化，如果知道更新顺序的话，就可以使用动态规划来提前计算出所有子问题的结果,从而避免重复计算。本质就是利用已经计算好的信息。
-
-
-
可重复选择:
-
递归回溯: 递归中根据是否选择当前元素来实现分支,注意在选择了的分支递归时,下一个递归传入的起始下标不变,以便实现重复选择当前元素。
这里和上面的不可重复选择的区别就在于递归调用时传入的下标不同,一个是i+1(不可重复),一个是i(可重复，下次还可以从i开始选择)。
void backtrack(vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) { result.push_back(current); // 将当前组合加入结果 for (int i = start; i < nums.size(); ++i) { current.push_back(nums[i]); // 选择当前元素 backtrack(nums, i, current, result); // 递归选择下一个元素，注意这里传入的是 i 而不是 i + 1 current.pop_back(); // 撤销选择，回溯 } }
-
- 已经生成了的序列
配对判断或者寻找对应的配对元素- 使用
栈：栈可以实现配对问题,如括号匹配问题,遇到左括号入栈,遇到右括号出栈,最后栈为空则表示配对成功。bool isValid(string s) { stack<char> st; for (char c : s) { if (c == '(' || c == '{' || c == '[') { st.push(c); } else { if (st.empty()) return false; char top = st.top(); st.pop(); if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) { return false; } } } return st.empty(); }
- 使用
- 需要生成配对的序列
递归回溯：利用左边匹配的元素个数必须大于等于右边匹配的元素个数这一性质,否则无法配对成功。
void backtrack(int left, int right, string& current, vector<string>& result) { if (left < 0 || right < 0 || right < left) { return; // 剪枝条件 } if (left == 0 && right == 0) { result.push_back(current); // 将当前组合加入结果 return; } current.push_back('('); // 选择左括号 backtrack(left - 1, right, current, result); // 递归选择下一个元素 current.pop_back(); // 撤销选择，回溯 current.push_back(')'); // 选择右括号 backtrack(left, right - 1, current, result); // 递归选择下一个元素 current.pop_back(); // 撤销选择，回溯 }
在一对匹配的括号中不同位置插入合法序列: 利用当前匹配的(a)b中的已经互相匹配的前后驱中，可以在a或者b的位置插入适合完整合法的序列，才能构造出当前的两个扩号是一对的unordered_map<int,string> record; vector<string> generateParenthesis(int n) { if(record.count(n)) return record[n]; // 使用记忆化避免重复计算 if (n == 0) return {""}; vector<string> result; for (int i = 0; i < n; ++i) { for (const string& left : generateParenthesis(i)) { for (const string& right : generateParenthesis(n - 1 - i)) { result.push_back("(" + left + ")" + right); } } } record[n] = result; // 记录结果，避免重复计算 return result; }
一对紧邻的括号插入合法序列: 在一对紧邻的括号中插入合法序列vector<string> generateParenthesis(int n) { if (n == 1) return {"()"}; unordered_map<string, int> a; vector<string> res; string tmp; for (auto& s: generateParenthesis(n - 1)) { for (int i = 0; i != 2 * (n - 1); ++i) { tmp = s.substr(0, i) + "()" + s.substr(i, 2 * (n - 1)); if (a[tmp] == 0) { // 避免重复 ++a[tmp]; res.emplace_back(tmp); } } } return res; }
- 使用
双指针法:void reverseString(vector<char>& s) { int left = 0, right = s.size() - 1; while (left < right) { swap(s[left], s[right]); left++; right--; } }
- 使用
标准库函数:#include <algorithm> void reverseString(vector<char>& s) { reverse(s.begin(), s.end()); }
- 使用
栈: 栈可以实现反序问题,使用递归函数也可以,因为递归本质上也是利用了系统栈的特性。#include <stack> void reverseString(vector<char>& s) { stack<char> st; for (char c : s) { st.push(c); } for (int i = 0; i < s.size(); i++) { s[i] = st.top(); st.pop(); } }
字母异位词：
是指两个有序组合中所有元素相同，但排列顺序不同的组合。比如 "listen" 和 "silent" 就是字母异位词。
优化技巧：
- 让这些组合以某个
规则(如字母升序、降序)进行排序，即可以将字母异位词归类到一起，方便后续处理。- 这里的
排序可以优化：- 通常使用
快速排序sort()，时间复杂度为 O(n log n)。 - 但对于
元素多而值域少，即相同元素重复较多的情况，可以使用计数排序(桶排)，时间复杂度可优化至 O(n)。
- 通常使用
- 这里的
简单但低效的方法：直接使用multiset进行存储和比较hash+链式(vector)方法：直接使用各元素值累加(或者其他去除位置因素的计算方法)作为索引,初步缩小搜索范围,优化搜索效率，然后再逐一元素比较。- 优点：
- 不用考虑位置因素
- 不用多次比较，只需要计算一次 hash 值，比较一次 hash 数值即可。
- 注意：不能直接使用
hash值进行比较，因为不同的组合(如af和be)可能会产生相同的 hash 值（哈希冲突），只能缩小范围，不能直接作为唯一标识。
- 优点：
- 桶排计数：
- 对于值域较小(如
字母串)，可以使用桶排计数每个字母出现的次数作为唯一标识; - 如果值域范围大，可以使用
哈希函数对计数结果进行压缩，得到一个较小的唯一标识，利用unorder_map进行存储和比较,因为unorder_map底层实现就是hash，可以实现O(1)的平均时间复杂度。
- 对于值域较小(如
- 双循环枚举(定一(后边界)法) 内循环从开始到达外循环当前位置，即可枚举所有
两个边界组合且不重复。可以理解为将两个动变边界转化为定住一个结尾边界,枚举另一个起始边界的问题。
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {// 当 以 i 作为结尾边界时，枚举所有起始边界 j
// 处理边界 (j, i)
}
}- 双指针枚举(夹逼法) 双指针分别指向
两个边界,根据某种条件移动左/右指针,实现剪枝优化。
int left = 0, right = n - 1;
while (left < right) {
int h = min(height[left], height[right]);
area = max(area, (right - left) * h);
while (height[left] <= h && left < right) left++; // 一定不满足条件，移动左指针，实现剪枝优化
while (height[right] <= h && left < right) right--; // 一定不满足条件，移动右指针，实现剪枝优化
}- 双指针法：
- 排序成
有序数组、 - 通过
左右指针向中间移动，寻找符合条件的两个数。
- 排序成
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) { // 找到一组解
res.push_back({nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++; // 跳过重复元素
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) { // 和小于目标值，左指针右移增大和
left++;
} else { // 和大于目标值，右指针左移减小和
right--;
}
}- 定义：拓扑排序是对有向无环图(DAG)的节点进行线性排序，使得对于每一条有向边 (u, v)，节点 u 在节点 v 之前出现。
常见问题：
- 依赖(先后)关系问题 本质上 也是判断有没有环，没有环则可以完成所有任务;有循环依赖则无法完成所有任务
- 是否存在环
解法：
- Kahn算法(基于入度的BFS)：正向顺序 / 谁先能开始做
- 计算每个节点的入度。
- 将所有入度为0的节点
(入度为0则代表没有还没准备好的前驱节点，可以开始工作)加入队列。 - 不断从队列中取出节点，加入拓扑排序结果，并将其邻居节点的入度减1，如果邻居节点的入度变为0，则加入队列。
- 如果最终拓扑排序结果包含所有节点，则图中无环；否则，存在环。
class Dag{
private:
vector<vector<int>> graph;
vector<int> inDegree;
public:
bool topologicalSort(){
int n=graph.size();
queue<int> q;
for(int i=0;i<n;i++){
if(inDegree[i]==0) q.push(i);
}
int count=0;
while(!q.empty()){
int node=q.front();
q.pop();
count++;
for(int neighbor:graph[node]){
inDegree[neighbor]--;
if(inDegree[neighbor]==0) q.push(neighbor);
}
}
return count==n; // 如果 count 等于节点数，说明无环
}
}- DFS(深度优先搜索)：反向顺序(溯源) / 在完成这项任务前，需要先完成哪些任务
- 使用递归 DFS 遍历图，记录每个节点的访问状态（未访问、正在访问、没有环状依赖）。
- 如果在 DFS 过程中遇到一个正在访问的节点，说明存在环。
- 否则，在完成对一个节点的所有邻居的访问后，将该节点加入拓扑排序结果。
class Dag{
private:
vector<vector<int>> graph;
vector<int> visitStatus; // 0: 未访问, 1: 正在访问, 2: 已访问且无环
public:
bool dfs(int node){
if(visitStatus[node]==1) return false; // 已经访问过，发现环
if(visitStatus[node]==2) return true; // 已经访问过且无环，直接返回
visitStatus[node]=1; // 标记为正在访问
for(int neighbor:graph[node]){
if(!dfs(neighbor)) return false; // 递归访问邻居，发现环则返回 false
}
visitStatus[node]=2; // 标记为已访问且无环
return true;
}
bool topologicalSort(){
int n=graph.size();
visitStatus.resize(n,0);
for(int i=0;i<n;i++){
if(visitStatus[i]==0){
if(!dfs(i)) return false; // 发现环，返回 false
}
}
return true; // 无环，返回 true
}
}缺点：只能判断是否有环，无法得到全局的具体的拓扑排序结果，只能得到某个点的拓扑排序结果(依赖关系链)。
常见表现：
- 最短路径
- 最少步数/跳数/操作数
解法:
- BFS(广度优先搜索)：
-
适用于无权图的最短路径问题，因为 BFS 会逐层扩展节点，保证第一次到达目标节点时所经过的路径是最短的。
-
使用队列存储当前层的节点，逐层遍历，直到找到目标节点。
-
使用
bfs队列方式模拟 同时从多个起点并同时开始搜索
-
int bfsShortestPath(GraphNode* start, GraphNode* target) {
queue<GraphNode*> q;
unordered_set<GraphNode*> visited; // 使用 hashset 判断有没有访问过，可以实现 O(1) 的查找
q.push(start);
visited.insert(start);
int steps = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
GraphNode* node = q.front();
q.pop();
if (node == target) {
return steps; // 找到目标节点，返回步数
}
for (GraphNode* neighbor : node->neighbors) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
steps++;
}
return -1; // 目标节点不可达
}- Dijkstra算法：
- 适用于边权非负的有权图的最短路径问题。
- 使用优先队列（最小堆）来选择当前距离起点最近的节点，逐步更新其邻居节点的距离，直到找到目标节点或遍历完所有节点。
- 定义：在一棵树中，节点
p和q的最近公共祖先是指一个节点x，满足x是p和q的祖先，并且x的深度尽可能大。 - 解法：
使用递归的方式，分别在左右子树中寻找 p 和 q，如果在某个子树中找到了其中一个节点，则返回该节点；如果在两个子树中都找到了节点，则当前节点就是最近公共祖先。
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr || root==p || root==q) return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left==nullptr) return right;
if(right==nullptr) return left;
return root;
}在递归回溯的过程中，对回溯经过的节点进行染色(标记)，当回溯到一个节点时，如果该节点已经被染色了，说明该节点是 p 和 q 的公共祖先。其实这个本质和上面的递归法是一样的,只是上面是隐式地通过函数调用栈来处理的。
对于频繁询问且修改少的方式,通过预处理树的父节点信息,每个节点维护一个father数组,其中father[i][j]表示节点 i 的第 2^j 个祖先节点。通过预处理，可以在 O(n log n) 的时间内构建这个父节点数组，然后在查询时，可以通过倒序枚举 j 从大到小，判断 p 和 q 的第 2^j 个祖先是否相同，如果不同，则将 p 和 q 分别移动到它们的第 2^j 个祖先节点，直到找到最近公共祖先 ; 如果相同，说明步数跳多了，不能跳，需要继续枚举更小的 j 进行判断，直到找到最近公共祖先。
一直往左儿子节点走，直到没有左儿子节点了，再回退到父节点。在一直往左走时，使用一个stack来存储当前节点的右节点还没遍历的父节点，等待当前节点没有左儿子节点了，就回退到父节点，继续往右走。
void dfs(TreeNode* root) {
stack<TreeNode*> st; // 存储当前节点的右节点还没遍历的父节点，便于回溯
TreeNode* cur = root;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) { // 当 cur 不为空时，继续往左走；当 cur 为空时，说明当前是走到了 null 节点，即上一轮走到了叶子节点，现在需要回退到父节点了
st.push(cur);
cur = cur->left; // 一直往左走
}
cur = st.top(); // 现在 cur 是 null 了，需要在 stack 中弹出最低还有右节点没有遍历的父节点了
st.pop();
cur = cur->right; // 因为栈中弹出的节点的左节点已经遍历完了，所以现在需要往右走了
}
}通过修改左子树的最右节点的右指针来实现迭代 dfs,这样相当于可以一条路不用回头,不需要额外空间存储父节点了
void dfs(TreeNode* root) {
TreeNode* cur = root;
while (cur != nullptr) { // 当 cur 不为空时，说明还没有遍历完所有节点
if (cur->left == nullptr) { // 没有左子树了，直接访问当前节点，然后往右走
// 访问 cur 节点
cur = cur->right;
} else { // 有左子树了，需要找到左子树的最右节点
TreeNode* pre = cur->left;
while (pre->right != nullptr && pre->right != cur) { // 找到左子树的最右节点 这里的 pre->right != cur 是为了判断是否已经建立了连接了，如果已经建立了连接了，说明左子树已经遍历完了，现在需要访问当前节点了，然后断开连接，往右走 (采用的是 中序遍历 的顺序，如果是前序遍历的话，这里就不需要判断是否已经建立了连接了，直接建立连接后访问当前节点，然后往左走即可)
pre = pre->right;
}
if (pre->right == nullptr) { // 还没有建立连接，建立连接后继续往左走
pre->right = cur; // 建立连接
cur = cur->left; // 往左走
} else { // 已经建立连接了，说明左子树已经遍历完了，现在需要访问当前节点了，然后断开连接，往右走
pre->right = nullptr; // 断开连接
// 访问 cur 节点
cur = cur->right; // 往右走
}
}
}
}- 堆(对于动态插入)：
- 使用一个大小为
k的最小堆来维护当前的前k大元素。 - 遍历输入的元素，对于每个元素，如果堆的大小小于
k，则直接将元素加入堆中；如果堆的大小等于k，则比较当前元素与堆顶元素（最小元素），如果当前元素更大，则弹出堆顶元素并将当前元素加入堆中。 - 最终，堆中的元素就是前
k大的元素。 时间复杂度为 O(n log k)，其中 n 是输入元素的数量，k 是需要找出的前 k 大元素的数量。
vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> frequency; // 统计每个元素的频率 for (int num : nums) { frequency[num]++; } auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; // 按照频率从小到大排序 }; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> minHeap(cmp); // 最小堆 for (const auto& entry : frequency) { minHeap.push(entry); // 将元素和频率加入堆中 if (minHeap.size() > k) { // 如果堆的大小超过 k，弹出堆顶元素 minHeap.pop(); } } vector<int> result; while (!minHeap.empty()) { result.push_back(minHeap.top().first); // 将堆顶元素的值加入结果 minHeap.pop(); } return result; }
- 使用一个大小为
- 快速选择算法(对于静态数组)：
nth_element算法可以在平均 O(n) 的时间复杂度内找到第k大的元素。通过使用nth_element，我们可以将数组分成两部分：前k大的元素和剩余的元素。然后，我们可以直接返回前k大的元素。vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> frequency; // 统计每个元素的频率 for (int num : nums) { frequency[num]++; } vector<pair<int, int>> freqVec(frequency.begin(), frequency.end()); // 将频率信息转换为向量 auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; // 按照频率从大到小排序 }; nth_element(freqVec.begin(), freqVec.begin() + k - 1, freqVec.end(), cmp); // 使用 nth_element 找到第 k 大的元素 vector<int> result; for (int i = 0; i < k; ++i) { result.push_back(freqVec[i].first); // 将前 k 大的元素加入结果 } return result; }
对比：
- 堆适用于需要动态插入元素的情况，而快速选择算法适用于静态数组的情况。
- 堆的时间复杂度为 O(n log k)，而快速选择算法的平均时间复杂度为O(n)，在实际应用中，快速选择算法通常比堆更快，尤其是当 k 较小的时候。
- 堆适用于当数据量非常大时，因为它只需要维护一个大小为 k 的堆，而快速选择算法需要对整个数组进行操作。
中位数实质上是一个特殊的第 k 大元素问题,其中 k 是数组长度的一半。对于中位数问题，我们可以使用与前 k 大元素类似的方法来解决。
- 双堆法：
- 使用一个最大堆来存储较小的一半元素，使用一个最小堆来存储较大的一半元素。
- 保持两个堆的大小平衡，或者最大堆的大小比最小堆大1。
- 当需要获取中位数时，如果两个堆的大小相等，则中位数是两个堆顶元素的平均值；如果最大堆的大小比最小堆大1，则中位数是最大堆的堆顶元素。
- 插入元素时，根据元素的值与当前中位数的关系，将元素插入到相应的堆中，并调整堆的大小以保持平衡。
- 时间复杂度为 O(log n) 用于插入元素，获取中位数的时间复杂度为 O(1)。
class MedianFinder { private: priority_queue<int> max_heap_; priority_queue<int, vector<int>, greater<int>> min_heap_; public: MedianFinder() { } void addNum(int num) { if(max_heap_.empty() || num <= max_heap_.top()) { max_heap_.push(num); if(max_heap_.size() > min_heap_.size() + 1) { min_heap_.push(max_heap_.top()); max_heap_.pop(); } }else{ min_heap_.push(num); if(min_heap_.size() > max_heap_.size()) { max_heap_.push(min_heap_.top()); min_heap_.pop(); } } } double findMedian() { if(max_heap_.size() > min_heap_.size()) { return max_heap_.top(); } else { return (max_heap_.top() + min_heap_.top()) / 2.0; } } };
- 红黑树：
- 使用一个平衡二叉搜索树（如红黑树）来存储所有元素，并维护一个指向中位数的指针。
- 插入元素时，根据元素的值与当前中位数的关系，将元素插入到树中，并调整指针以保持指向正确的中位数。
- 获取中位数的时间复杂度为 O(1)，插入元素的时间复杂度为 O(log n)。
class MedianFinder { private: multiset<int> nums; // 使用 multiset 来存储元素，保持有序 multiset<int>::iterator left, right; public: MedianFinder() : left(nums.end()), right(nums.end()) {} void addNum(int num) { const size_t n = nums.size(); nums.insert(num); if (!n) { left = right = nums.begin(); } else if (n & 1) { if (num < *left) { left--; } else { right++; } } else { if (num > *left && num < *right) { left++; right--; } else if (num >= *right) { left++; } else { right--; left = right; } } } double findMedian() { return (*left + *right) / 2.0; } };
- 快速选择算法：
- 使用快速选择算法来找到数组中第
n/2小的元素（如果数组长度为奇数）或第n/2 - 1和第n/2小的元素（如果数组长度为偶数），然后计算中位数。 - 时间复杂度为 O(n) 平均情况下，最坏情况下为 O(n^2)。
直接使用
kth_element算法来找到第n/2小的元素（如果数组长度为奇数）或第n/2 - 1和第n/2小的元素（如果数组长度为偶数），然后计算中位数。
- 使用快速选择算法来找到数组中第
- 动态数据流中的中位数问题,
multiset的底层实现是红黑树，在每次动态调整中充分利用了之前已经调整好了的结果，所以可以实现O(log n)的插入时间复杂度，而双堆法更加简单，它也充分利用了排序的结果，但在调整过程中可以不用保证全部元素有序，只有堆顶元素需要满足条件，所以在调整过程中可以更快一些，平均时间复杂度为 O(log n)，在实际应用中，双堆法通常比红黑树更快，尤其是当数据量较大时。 - 静态数组中的中位数问题,
快速选择算法的kth_element算法在平均情况下的时间复杂度为O(n),可以不用对整个数组进行排序，而是通过分区的方式来找到第n/2小的元素，这样在实际应用中通常比使用堆更快，尤其是当数组长度较大时。
当有大量序列信息且单个序列元素值域范围不大(如字符串)时，可以使用字典树(Trie)对这些序列信息基于前缀信息进行记忆存储
常见应用场景：
- 自动补全系统
- 拼写检查
前缀匹配查询 (后面分枝)
优点：
- 这样基于树的结构，大量序列信息必然出现很多相同的前缀,这样共享前缀可以节省存储空间,在末尾再进行分流（分枝），这样也为自动补全提供了便利,不用当一个元素匹配失败时重新开始匹配另一个重走了一遍前面的相同前缀。
与 hash 映射对比：
-
Trie适用于需要频繁进行前缀查询的场景，且序列元素值域较小且记忆的元素非常多的情况。 -
Hash function转化为32进制进行存储:-
优点： 对于
完整序列的比较，只要比较hash值即可，速度非常快。 -
缺点：
- 无法进行
前缀查询,因为序列长度不同，无法确定前缀的hash值向前移动多少位单位进制即$*base^k$ (k 移动的位数）。 - 如果要
记忆的元素非常多，这种方法每个元素都需要存储一个hash值，存储空间开销较大。 -
序列长度非常长时，C++ 中的基本数据类型可能无法存储完整的hash值，可能需要使用大数库，增加实现复杂度。
- 无法进行
-
优点： 对于
class Trie {
private:
struct TrieNode_{
bool isEnd;
vector<TrieNode_*> next;
TrieNode_():isEnd(false),next(26,nullptr){}
};
TrieNode_* root_;
public:
Trie() {
root_ = new TrieNode_();
}
void insert(string word) {
insert_(root_, word);
}
bool search(string word) {
TrieNode_* root=this->root_;
for(const char& c:word){
if(root->next[c-'a']==nullptr) return false;
root=root->next[c-'a'];
}
return root->isEnd;
}
bool startsWith(string prefix) {
TrieNode_* root=this->root_;
for(const char& c:prefix){
if(root->next[c-'a']==nullptr) return false;
root=root->next[c-'a'];
}
return true;
}
private:
void insert_(TrieNode_* root,string& word){
if(word.empty())return;
char c=word[0];
if(root->next[c-'a']==nullptr) {
root->next[c-'a']=new TrieNode_();
}
word.erase(word.begin(),word.begin()+1);
if(word.empty()){
root->next[c-'a']->isEnd=true;
return;
}
insert_(root->next[c-'a'],word);
return;
}
};- 单调栈 是一种特殊的栈结构，栈内元素保持单调递增或单调递减的顺序。
- 特点：
- 存储顺序：栈内元素按照某种顺序排列（递增或递减）。
- 操作规则：在入栈时，若新元素违反了单调性，则弹出栈顶元素，直到栈内元素重新满足单调性,这样相当于将前面比当前元素小的元素都"清除"掉了，直接压缩掉了不必要的比较，后面比较时就不需要再考虑这些元素了，只需要直接考虑这个大的元素即可。
- 应用场景：
- 常用于解决需要频繁查询
最大值或最小值的问题，如滑动窗口最大值、柱状图中的最大矩形面积等。 - 栈中元素存储都是大于当前元素的元素，即可以查询前面
大于当前元素的最近元素,因为出栈压缩处理省去了很多不必要的比较。
- 常用于解决需要频繁查询
for(int i=0;i<nums.size();i++){
while(!st.empty()&&st.top()<=nums[i]){
st.pop();
}
st.push(nums[i]); // 技巧: 如果需要存储的值有序,可以存储索引而不是值本身，存索引相当于存了值，因为可以通过运行时间接访问获取值。
} - 典型应用：
- 229.滑动窗口最大值
- 思路：固定大小的滑动窗口，寻找每次滑动时的最大值。则定住
右边界，维护一个单调栈，则单调栈里维护的都是比当前右边界值大的元素，每次要实现进一步修改(突破)的元素的时候所需要访问的元素(因为栈顶是比当前元素大的最近的元素，如果需要再突破，就要走到栈顶倒数第二元素的位置才有可能增大了，突破了)。由于有窗口大小限制，所以在栈里面存索引，方便判断是否在窗口内，而且是升序，在栈里找在索引范围内的可以可以实现突破的依次索引值，其中第一个在索引范围内的就是当前窗口的最大值。
vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> st; vector<int> ret; for(int i=0;i<nums.size();i++){ while(!st.empty()&&nums[st.back()]<=nums[i]){ st.pop_back(); } st.push_back(i); if(i<k-1)continue; vector<int>::iterator it=lower_bound(st.begin(),st.end(),i-k+1); ret.push_back(nums[*it]); } return ret; }
- 这个题目还可以理解为：以右边界这个数为起点，不断向左突破
k个数，找到k个数中最大的那个数。
- 思路：固定大小的滑动窗口，寻找每次滑动时的最大值。则定住
- 229.滑动窗口最大值
- 稀疏表 是一种用于高效查询**静态(不动态修改值)**数组区间最值(
RMQ,静态区间最值查询)的数据结构. - 实现步骤：
- 预处理：构建稀疏表，时间复杂度为 O(n log n)。
- 查询：使用预处理好的稀疏表进行区间最值查询，时间复杂度为 O(1)。
#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; const int MAXN = 100005; const int K = 20; // 2^20 > 100000，足够覆盖最大长度 int st[MAXN][K]; // ST表数组 int lg[MAXN]; // 预处理 log 值，避免使用 std::log2 函数太慢,而且经常访问 // 1. 预处理 Log 数组 (求 log2(i) 向下取整) void initLog(int n) { lg[1] = 0; for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1; // log(i)=log(i/2*2)=log(i/2)+1 } // 2. 构建 ST 表 void buildST(const vector<int>& arr) { int n = arr.size(); // 初始化长度为 1 的区间 for (int i = 0; i < n; i++) st[i][0] = arr[i]; // 倍增计算 // j 代表长度指数，i 代表起点 for (int j = 1; j <= K; j++) { for (int i = 0; i + (1 << j) - 1 < n; i++) { st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]); } } } // 3. 查询 int query(int L, int R) { int k = lg[R - L + 1]; // 两个区间：从 L 开始长 2^k，和从 R 结尾长 2^k return max(st[L][k], st[R - (1 << k) + 1][k]); } int main() { vector<int> nums = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10}; initLog(nums.size()); buildST(nums); cout << "Max in [2, 6] (5, 7, 9, 2, 4): " << query(2, 6) << endl; // 输出 9 return 0; }
- 预处理：构建稀疏表，时间复杂度为 O(n log n)。
- 适用场景：
- 适用于需要频繁查询数组区间(区间可以变化)
最值的场景，且数组内容不发生变化的情况。
- 这里每一个
j层对应处理不同区间长度的查询。如果查询长度是固定的,可以不用构建完整的稀疏表,只需要构建对应长度的那一层即可,节省空间和预处理时间,不过有稍微改动.采用滑动窗口最大值的思路,或者分块+预处理的方法即可。 即：先将分块成n[nk]~n[n(k+1)-1]，然后每次查询必落在两块之间，即max(preMax[r], sufMax[l])，其中preMax表示每块的前缀最大值，sufMax表示每块的后缀最大值。class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); vector<int> prefixMax(n), suffixMax(n); for (int i = 0; i < n; ++i) { if (i % k == 0) { prefixMax[i] = nums[i]; } else { prefixMax[i] = max(prefixMax[i - 1], nums[i]); } } for (int i = n - 1; i >= 0; --i) { if (i == n - 1 || (i + 1) % k == 0) { suffixMax[i] = nums[i]; } else { suffixMax[i] = max(suffixMax[i + 1], nums[i]); } } vector<int> ans; for (int i = 0; i <= n - k; ++i) { ans.push_back(max(suffixMax[i], prefixMax[i + k - 1])); } return ans; } };
- 适用于需要频繁查询数组区间(区间可以变化)
-
树状数组 (Fenwick Tree) 是一种用于高效处理
数组前缀(区间和)和查询和单点更新的数据结构。
同lowbit的节点属于同一层，属于兄弟，父节点为lowbit的两倍,每个节点管理着lowbit个元素。 -
注意: 开始必须
索引从1开始,即tree[0]不存储任何值,方便计算父节点和子节点。 -
实现步骤：
- 初始化：构建树状数组，时间复杂度为 O(n log n)。
- 更新：更新数组中的某个元素，时间复杂度为 O(log n)。
- 查询：查询数组的前缀和，时间复杂度为 O(log n)。
class FenwickTree { private: vector<int> tree; int n; public: FenwickTree(int size) : n(size) { tree.resize(n + 1, 0); // 树状数组索引从1开始 } // 更新操作: 在索引 idx 处增加 delta void update(int idx, int delta) { while (idx <= n) { tree[idx] += delta; idx += idx & -idx; // 移动到下一个节点 } } // 查询操作: 获取前缀和 [1, idx] int query(int idx) { int sum = 0; while (idx > 0) { sum += tree[idx]; idx -= idx & -idx; // 移动到父节点 } return sum; } // 获取区间和 [left, right] int rangeQuery(int left, int right) { return query(right) - query(left - 1); } };
- 适用场景：
- 适用于需要频繁进行
前缀和(区间和)查询、区间最大值和单点更新的场景，如动态数组求和、频率统计等。 - 如果需要处理
区间更新和区间查询，可以考虑使用差分数组结合树状数组，或者使用线段树.
- 适用于需要频繁进行
线段树 (Segment Tr) 是一种用于高效处理数组区间查询和区间更新的数据结构。
应用场景：
-
动态修改数组中的元素值。 -
频繁查询数组的
区间和、区间最值等。 -
适用于需要处理
区间更新和区间查询的场景,树状数组无法满足需求时使用。 实现步骤： -
构建：构建线段树，时间复杂度为 O(n)
-
更新：更新数组中的某个元素，时间复杂度为 O(log n)
-
查询：查询数组的区间和，时间复杂度为 O(log n)
class SegmentTree {
private:
vector<int> tree;
int n;
public:
SegmentTree(int size) : n(size) {
tree.resize(4 * n, 0); // 线段树大小一般为 4n
}
void pushUp(int node) {
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
// 构建线段树
void build(const vector<int>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
pushUp(node);
}
}
// 更新操作: 在索引 idx 处更新为 val
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
update(2 * node, start, mid, idx, val);
} else {
update(2 * node + 1, mid + 1, end, idx, val);
}
pushUp(node);
}
}
// 查询操作: 获取区间和 [L, R]
int query(int node, int start, int end, int L, int R) {
if (R < start || end < L) {
return 0; // 区间不重叠
}
if (L <= start && end <= R) {
return tree[node]; // 区间完全重叠
}
int mid = (start + end) / 2;
int p1 = query(2 * node, start, mid, L, R);
int p2 = query(2 * node + 1, mid + 1, end, L, R);
return p1 + p2; // 合并结果
}
};
- 区间修改：如果需要对一个区间内的所有元素进行加法、赋值等操作，并且仍然要求高效的区间查询，线段树需要支持懒惰标记（Lazy Propagation）。
- 懒惰标记：当对某个区间进行修改时，暂时不递归修改所有子节点，而是打上标记，等到需要用到子节点时再进行下传和更新，避免重复操作，提高效率。
示例：区间加法的懒惰标记线段树实现（伪代码）：
class SegmentTree {
private:
vector<int> tree, lazy;
int n;
public:
SegmentTree(int size) : n(size) {
tree.resize(4 * n, 0);
lazy.resize(4 * n, 0);
}
void pushUp(int node) {
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void pushDown(int node, int start, int end) {
if (lazy[node] != 0) {
int mid = (start + end) / 2;
tree[2 * node] += (mid - start + 1) * lazy[node];
tree[2 * node + 1] += (end - mid) * lazy[node];
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
lazy[node] = 0;
}
}
// 区间加法更新 [l, r] 区间加 val
void updateRange(int node, int start, int end, int l, int r, int val) {
if (r < start || end < l) return;
if (l <= start && end <= r) {
tree[node] += (end - start + 1) * val;
lazy[node] += val;
return;
}
pushDown(node, start, end);
int mid = (start + end) / 2;
updateRange(2 * node, start, mid, l, r, val);
updateRange(2 * node + 1, mid + 1, end, l, r, val);
pushUp(node);
}
// 区间查询 [L, R]
int query(int node, int start, int end, int L, int R) {
if (R < start || end < L) return 0;
if (L <= start && end <= R) return tree[node];
pushDown(node, start, end);
int mid = (start + end) / 2;
return query(2 * node, start, mid, L, R) + query(2 * node + 1, mid + 1, end, L, R);
}
};- 适用场景：需要频繁对区间进行加法、赋值等操作，并且需要高效查询区间和、区间最值等。
- 动态修改：(
线段树或者树状数组)- 单点修改：使用
树状数组或线段树，时间复杂度 O(log n) - 区间修改：使用
线段树(带懒惰标记)，时间复杂度 O(log n)
- 单点修改：使用
- 静态:(不修改数组值)
- 在线查询：使用
稀疏表，时间复杂度 O(1) - 离线查询：使用
单调栈,预先指导所有要查询的区间即称为离线查询，时间复杂度 O(n)
- 在线查询：使用
- 区间查询：
- 区间和：使用
树状数组或线段树，时间复杂度 O(log n) - 区间最值：使用
稀疏表(静态数组)或线段树(动态数组)，时间复杂度 O(1) 或 O(log n)
- 区间和：使用
| 数据结构 | 适用场景及对应复杂度 |
|---|---|
| 线段树 | 1. 区间和 O(log n) 2.区间最值 O(log n) 3.区间修改(独有)O(log n) |
| 树状数组 | 1. 区间和 O(log n) 2.单点修改 O(log n) |
| 稀疏表 | 1. 区间最值 O(1) (静态数组) |
| 单调栈 | 1. 区间最值 O(n) (离线查询) |
| 前缀和数组 | 1. 区间和 O(1) (静态数组) |
| 差分数组 | 1. 区间修改 O(1) (静态数组) |