做外贸的社交网站,cnn头条新闻,有网站如何做直播,可以做试卷的网站英语七. 贪心算法 文章目录 七. 贪心算法1. 605 种花问题2. 121 买卖股票的最佳时机3. 561 数组拆分4. 455 分发饼干5. 575 分糖果6. 135 分发糖果7. 409 最长回文串8. 621 任务调度器9. 179 最大数10. 56 合并区间11. 57 插入区间13. 452 用最少数量的箭引爆气球14. 435 无重叠区间…七. 贪心算法 文章目录 七. 贪心算法1. 605 种花问题2. 121 买卖股票的最佳时机3. 561 数组拆分4. 455 分发饼干5. 575 分糖果6. 135 分发糖果7. 409 最长回文串8. 621 任务调度器9. 179 最大数10. 56 合并区间11. 57 插入区间13. 452 用最少数量的箭引爆气球14. 435 无重叠区间15. 646 最长数对链16. 406 按照身高重建队列17. 48 旋转图像18. 169 多数元素19. 215 数组中的第k个最大元素20. 75 颜色分类21. 324 摆动顺序II22. 517 超级洗衣机[未解]23. 649 Dota2 参议院24. 678 有效的括号字符串25. 420 强密码检验器26. 53 最大子数组和27. 134 加油站28. 581 最短无序连续子数组29. 152 乘积最大子数组30. 334 递增的三元子序列31. 376 摆动序列32. 659 分割数组为连续子序列33. 343 整数拆分34. 496 下一个更大元素I35. 503 下一个更大的元素||36. 456 132模式37. 316 去除重复字母38. 402 移掉k位数字39. 321 拼接最大数40. 84 柱状图中最大的矩形41. 85 最大矩形 题目分类 题目编号数组与贪心算法 605、121、122、561、455、575、135、409、621、179、56、57、228、452、435、646、406、48、169、215、75、324、517、649、678、420子数组与贪心算法 53、134、581、152子序列与贪心算法 334、376、659数字与贪心 343单调栈法 496、503、456、316、402、321、84、85
1. 605 种花问题 解法贪心算法
我们直接遍历数组flowerbed对于每个位置 iii如果flowerbed[i]0并且其左右相邻位置都为 0则我们可以在该位置种花否则不能。最后我们统计可以种下的花的数量如果其不小于 n则返回 true否则返回 false。
代码
class Solution {
public:bool canPlaceFlowers(vectorint flowerbed, int n) {int lenflowerbed.size();if(n0)return true;for(int i0;ilen;i){if(i0flowerbed[i]0){if(len1||flowerbed[i1]0){n--;flowerbed[i]1;}}else if(ilen-1flowerbed[i]0){if(flowerbed[i-1]0){n--;flowerbed[i]1;}}else{if(flowerbed[i]0flowerbed[i-1]0flowerbed[i1]0){n--;flowerbed[i]1;}}if(n0)return true;}return false;}
};注意有种简洁的代码描述方式比上述代码来的简洁的多 class Solution {
public:bool canPlaceFlowers(vectorint flowerbed, int n) {int m flowerbed.size();for (int i 0; i m; i) {int l i 0 ? 0 : flowerbed[i - 1];int r i m - 1 ? 0 : flowerbed[i 1];if (l flowerbed[i] r 0) {flowerbed[i] 1;--n;}}return n 0;}
};
时间复杂度O(n)其中 n 是数组 flowerbed的长度。只需要遍历数组一次。
空间复杂度: O(1)。
2. 121 买卖股票的最佳时机 解法1一次遍历
假设给定的数组为[7, 1, 5, 3, 6, 4]
我们来假设自己来购买股票。随着时间的推移每天我们都可以选择出售股票与否。那么假设在第 i 天如果我们要在今天卖股票那么我们能赚多少钱呢
显然如果我们真的在买卖股票我们肯定会想如果我是在历史最低点买的股票就好了在题目中我们只要用一个变量记录一个历史最低价格 minPrice我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minPrice。
因此我们只需要遍历价格数组一遍记录历史最低点然后在每一天考虑这么一个问题如果我是在历史最低点买进的那么我今天卖出能赚多少钱当考虑完所有天数之时我们就得到了最好的答案。
代码
class Solution {
public:int maxProfit(vectorint prices) {int lenprices.size();if(len2)return 0;int minPriceprices[0],maxProfit0;for(int p:prices){maxProfitmax(maxProfit,p-minPrice);minPricemin(p,minPrice);}return maxProfit;}
};时间复杂度O(n) 只遍历了一次
空间复杂度O(1) 只使用了常量个变量。
解法2: 动态规划
思路题目只问最大利润没有问这几天具体哪一天买、哪一天卖因此可以考虑使用 动态规划 的方法来解决。
买卖股票有约束根据题目意思有以下两个约束条件
条件 1你不能在买入股票前卖出股票 条件 2最多只允许完成一笔交易。 因此 当天是否持股 是一个很重要的因素而当前是否持股和昨天是否持股有关系为此我们需要把 是否持股 设计到状态数组中。
dp[i][j]下标为 i 这一天结束的时候手上持股状态为 j 时我们持有的现金数。换种说法dp[i][j] 表示天数 [0, i] 区间里下标 i 这一天状态为 j 的时候能够获得的最大利润。其中
j 0表示当前不持股 j 1表示当前持股。
注意下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息因此最后输出 dp[len - 1][0]。
使用「现金数」这个说法主要是为了体现 买入股票手上的现金数减少卖出股票手上的现金数增加 这个事实 「现金数」等价于题目中说的「利润」即先买入这只股票后买入这只股票的差价
推导状态转移方程
dp[i][0]规定了今天不持股有以下两种情况 昨天不持股今天什么都不做 昨天持股今天卖出股票现金数增加
dp[i][1]规定了今天持股有以下两种情况
昨天持股今天什么都不做现金数与昨天一样昨天不持股今天买入股票注意只允许交易一次因此手上的现金数就是当天的股价的相反数。
代码
class Solution {
public:int maxProfit(vectorint prices) {int lenprices.size();if(len2)return 0;int dp[len][2];// dp[i][0] 下标为 i 这天结束的时候不持股手上拥有的现金数// dp[i][1] 下标为 i 这天结束的时候持股手上拥有的现金数dp[0][0]0;dp[0][1]-prices[0];for(int i1;ilen;i){dp[i][0]max(dp[i-1][0],dp[i-1][1]prices[i]);dp[i][1]max(dp[i-1][1],-prices[i]);}return dp[len-1][0];}
};时间复杂度O(N)遍历股价数组可以得到最优解空间复杂度O(N)状态数组的长度为 N。
3. 561 数组拆分 解法排序
我们先对数组进行排序。由于每两个数我们只能选择当前小的一个进行累加。因此我们猜想应该从第一个位置进行选择然后隔一步选择下一个数。这样形成的序列的求和值最大。
我们用反证法来证明下为什么这样选择的序列的求和值一定是最大的
猜想对数组进行排序从第一个位置进行选择然后隔一步选择下一个数。这样形成的序列的求和值最大下图黑标代表当前被选择的数字。 之所以我们能这么选择是因为每一个被选择的数的「下一位位置」都对应着一个「大于等于」当前数的值假设位置为 k 使得当前数在 min(a,b) 关系中能被选择下图红标代表保证前面一个黑标能够被选择的辅助数。 假如我们这样选择的序列求和不是最大值那么说明至少我们有一个值选错了应该选择更大的数才对。
那么意味着我们「某一位置」的黑标应该从当前位置指向更后的位置。
PS. 因为要满足 min(a, b) 的数才会被累加因此每一个红标右移变大必然导致原本所对应的黑标发生「同样程度 或 不同程度」的右移变大
这会导致我们所有的红标黑标同时往后平移。
最终会导致我们最后一个黑标出现在最后一位这时候最后一位黑标不得不与我们第 k 个位置的数形成一对。 我们看看这是求和序列的变化 k 位置前的求和项没有发生变化我们从 k 位置开始分析
原答案 nums[k] nums[k 2] … nums[n - 1] 调整后答案 nums[k 1] nums[k 3] … nums[n - 2] min(nums[n], nums[k]) 由于 min(nums[n], nums[k]) 中必然是 nums[k] 被选择。因此 调整后答案 nums[k] nums[k 1] nums[k 3] … nums[n - 2] 显然从原答案的每一项都「大于等于」调整后答案的每一项因此不可能在「假想序列」中通过选择别的更大的数得到更优解假想得证。
代码
class Solution {
public:int arrayPairSum(vectorint nums) {sort(nums.begin(),nums.end());int sum0;for(int i0;inums.size()-1;i2){summin(nums[i],nums[i1]);}return sum;}
};时间复杂度O(nlogn)即对数组nuts进行排序的时间复杂度
空间复杂度O(logn) 排序所需要使用的栈空间
4. 455 分发饼干 解法双指针贪心
为了尽可能满足最多数量的孩子从贪心的角度考虑应该按照孩子的胃口从小到大的顺序依次满足每个孩子且对于每个孩子应该选择可以满足这个孩子的胃口且尺寸最小的饼干。证明如下。
假设有 m 个孩子胃口值分别是 g 1 g_1 g1到 g m g_m gm有 n块饼干尺寸分别是 s 1 s_1 s1到 s n s_n sn满足 g i ≤ g i 1 g_i \le g_{i1} gi≤gi1和 s j ≤ s j 1 s_j \le s_{j1} sj≤sj1 其中 1 ≤ i m 1 \le i m 1≤im 1 ≤ j n 1 \le j n 1≤jn。
假设在对前 i−1 个孩子分配饼干之后可以满足第 i 个孩子的胃口的最小的饼干是第 j 块饼干即 s j s_j sj是剩下的饼干中满足 g i ≤ s j g_i \le s_j gi≤sj的最小值最优解是将第 j块饼干分配给第 i个孩子。如果不这样分配考虑如下两种情形
如果 im 且 g i 1 ≤ s j g_{i1} \le s_j gi1≤sj也成立则如果将第 j 块饼干分配给第 i1个孩子且还有剩余的饼干则可以将第 j1 块饼干分配给第 iii 个孩子分配的结果不会让更多的孩子被满足
如果 jn则如果将第 j1 块饼干分配给第 i个孩子当 g i 1 ≤ s j g_{i1} \le s_j gi1≤sj时可以将第 j块饼干分配给第 i1 个孩子分配的结果不会让更多的孩子被满足当 g i 1 s j g_{i1}s_j gi1sj时第 j 块饼干无法分配给任何孩子因此剩下的可用的饼干少了一块因此分配的结果不会让更多的孩子被满足甚至可能因为少了一块可用的饼干而导致更少的孩子被满足。
基于上述分析可以使用贪心的方法尽可能满足最多数量的孩子。
首先对数组 g 和 s 排序然后从小到大遍历 g 中的每个元素对于每个元素找到能满足该元素的 s 中的最小的元素。具体而言令 i 是 g 的下标j是 s的下标初始时 i 和 j 都为 0进行如下操作。
对于每个元素 g[i]找到未被使用的最小的 j使得 g [ i ] ≤ s [ j ] g[i] \le s[j] g[i]≤s[j]则 s[j] 可以满足 g[i]。由于 g 和 s 已经排好序因此整个过程只需要对数组 g 和 s 各遍历一次。当两个数组之一遍历结束时说明所有的孩子都被分配到了饼干或者所有的饼干都已经被分配或被尝试分配可能有些饼干无法分配给任何孩子此时被分配到饼干的孩子数量即为可以满足的最多数量。
代码
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {int count0;int sizeGg.size();int sizeSs.size();sort(g.begin(),g.end());sort(s.begin(),s.end());int i0;int j0;while(isizeGjsizeS){if(g[i]s[j]){j;}else{i;j;count;}}return count;}
};时间复杂度O(mlogmnlogn)其中 m 和 n 分别是数组 g 和 s 的长度。对两个数组排序的时间复杂度是 O(mlogmnlogn)遍历数组的时间复杂度是 O(mn)O(mn)O(mn)因此总时间复杂度是 O(mlogmnlogn)。
空间复杂度O(logmlogn)其中 m 和 n 分别是数组 g和 s的长度。空间复杂度主要是排序的额外空间开销。
5. 575 分糖果 解法贪心
设糖果的数量为n因为最多只能分到一半的糖果答案不会超过 n 2 \frac{n}{2} 2n;设置糖果的种类个数为numCandyType答案也不会超过numCandyType。
利用set对candyType进行去重得到numCandyType的糖果种类个数
很显然如果 n 2 n u m T y p e \frac{n}{2}numType 2nnumType最多只能吃numType种类的糖果否则 n 2 ≤ n u m T y p e \frac{n}{2}\leq numType 2n≤numType则最多也只能吃到 numType种的糖果 注意使用unordered_set的性能在此时大于set 底层数据结构 std::set 是基于平衡二叉搜索树通常是红黑树实现的它保持元素有序因此插入、删除和查找的时间复杂度都是 O(log n)。std::unordered_set 是基于哈希表实现的它使用哈希函数将元素映射到桶中插入、删除和查找的平均时间复杂度是 O(1)。 性能比较 在大多数情况下std::unordered_set 的操作更快因为哈希表通常能够提供更快的查找和插入操作。然而在某些特定情况下例如数据量较小或有序插入std::set 的性能可能更好因为它不需要处理哈希冲突而且红黑树的有序性可能在某些操作上产生优势。 迭代顺序 std::set 保持元素有序因此在迭代时元素以升序顺序出现。std::unordered_set 不保持元素的顺序迭代时元素的顺序是不确定的。 选择适当容器 选择使用哪种容器应取决于你的使用场景和需求。如果你需要有序性并且能够接受较慢的插入和查找可以选择 std::set。如果你更关注插入和查找的性能并且不需要有序性可以选择 std::unordered_set。 代码
class Solution {
public:int distributeCandies(vectorint candyType) {std::setintCandyTypeSet(candyType.begin(),candyType.end());int numCandyTypeCandyTypeSet.size();int ncandyType.size();if(n/2numCandyType){return numCandyType;}return n/2;}
};时间复杂度O(n)其中 n 是数组 CandyTypeSet 的长度。
空间复杂度O(n)。CandyTypeSet的哈希表需要O(n) 的空间。
6. 135 分发糖果 解法一贪心算法
规则定义 设学生 A 和学生 B 左右相邻A在 B 左边 左规则 当 ratings[B]ratings[A]时候B 的糖比 A 的糖数量多。 右规则 当 ratings[A]ratings[B]时A 的糖比 B 的糖数量多。 相邻的学生中评分高的学生必须获得更多的糖果 等价于 所有学生满足左规则且满足右规则。
根据以上规则我们可以从左向右按照左规则遍历一遍再从右向左按照右规则遍历一遍之后每次都取位置i的糖果最大数目可以保证即满足左规则又满足了右边规则
算法流程
先从左至右遍历学生成绩 ratings按照以下规则给糖并记录在 left 中先给所有学生 1颗糖
若 ratings[i]ratings[i−1]则第 i名学生糖比第 i−1 名学生多 1 个。
若 ratings[i]ratings[i−1] 则第 i名学生糖数量不变。交由从右向左遍历时处理。
经过此规则分配后可以保证所有学生糖数量 满足左规则 。 同理在此规则下从右至左遍历学生成绩并记录在 right 中可以保证所有学生糖数量 满足右规则 。
最终取以上 2轮遍历 left 和 right 对应学生糖果数的最大值 这样则 同时满足左规则和右规则 即得到每个同学的最少糖果数量。
【此过程可以在从右往左遍历右规则时完成】
代码
class Solution {
public:int candy(vectorint ratings) {int nratings.size();int left[n];std::fill(left,leftn,1);int right[n];std::fill(right,rightn,1);for(int i1;in;i){if(ratings[i]ratings[i-1]){left[i]left[i-1]1;}}int countleft[n-1];for(int in-2;i0;i--){if(ratings[i]ratings[i1]){
#从右边往左时候递归记录的是最后一个位置的糖果个数一直递归影响到前面位置的糖果个数 right[i]right[i1]1;}countmax(left[i],right[i]);}return count;}
};时间复杂度O(n)其中 n 是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度O(n)其中 n 是孩子的数量。我们需要保存所有的左规则对应的糖果数量。
解法二常数空间遍历
参考力扣官方题解135. 分发糖果 - 力扣LeetCode
注意到糖果总是尽量少给且从 11开始累计每次要么比相邻的同学多给一个要么重新置为 1。依据此规则我们可以画出下图 上述为例子[1,3,5,2,3,3]的最后的解 其中相同颜色的柱状图的高度总恰好为 1,2,3…。 而高度也不一定一定是升序也可能是 …3,2,1的降序 上述为数组[1,3,5,3,2,2]的解 注意到在上图中对于第三个同学他既可以被认为是属于绿色的升序部分也可以被认为是属于蓝色的降序部分。因为他同时比两边的同学评分更高。我们对序列稍作修改
注意到右边的升序部分变长了使得第三个同学不得不被分配 4个糖果。依据前面总结的规律我们可以提出本题的解法。我们从左到右枚举每一个同学记前一个同学分得的糖果数量为 pre如果当前同学比上一个同学评分高说明我们就在最近的递增序列中直接分配给该同学 pre1 个糖果即可。否则我们就在一个递减序列中我们直接分配给当前同学一个糖果并把该同学所在的递减序列中所有的同学都再多分配一个糖果以保证糖果数量还是满足条件。我们无需显式地额外分配糖果只需要记录当前的递减序列长度即可知道需要额外分配的糖果数量。同时注意当当前的递减序列长度和上一个递增序列等长时需要把最近的递增序列的最后一个同学也并进递减序列中。这样我们只要记录当前递减序列的长度 dec最近的递增序列的长度 inc 和前一个同学分得的糖果数量 pre 即可。
代码
class Solution {
public:int candy(vectorint ratings) {int nratings.size();int ret1;int inc1,dec0,pre1;for(int i1;in;i){if(ratings[i]ratings[i-1]){//将递减序列的个数清0dec0;preratings[i]ratings[i-1]?1:pre1;retpre;incpre;}else{//递减序列记录递减序列的值dec;//标志位置相同如123321此时递增序列的末尾3必须加1合并到递减序列中if(decinc){dec;}retdec;//pre还原为初始值1为了后续递增准备pre1;}}return ret;}
};时间复杂度O(n)其中 n 是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度O(1)。我们只需要常数的空间保存若干变量。
7. 409 最长回文串 解法贪心算法
回文串是一个正着读和反着读都一样的字符串。以回文中心为分界线对于回文串中左侧的字符 ch在右侧对称的位置也会出现同样的字符。例如在字符串 “abba” 中回文中心是 “ab|ba” 中竖线的位置而在字符串 “abcba” 中回文中心是 “ab©ba” 中的字符 “c” 本身。我们可以发现在一个回文串中只有最多一个字符出现了奇数次其余的字符都出现偶数次。
我们可以将每个字符使用偶数次使得它们根据回文中心对称。在这之后如果有剩余的字符我们可以再取出一个作为回文中心。
算法
首先利用letterToCount统计字符串中每个字符出现的个数设置结果为result,然后遍历letterToCount的value如果value是偶数则直接与result相加如果value是奇数则将value-1与result相加并且flag设置为1最后若flag为1就说明字符中有单个的字符存在可以作为回文串中的中心点因此将result;
class Solution {
public:int longestPalindrome(string s) {unordered_mapchar,intletterToCount;for(auto letter:s){letterToCount[letter];}int result0;int flag0;for(auto itletterToCount.begin();it!letterToCount.end();it){if(it-second%20){resultit-second;}else{result(it-second-1);flag1;}}if(flag)result;return result;}
};时间复杂度O(N)其中 N 为字符串 s 的长度。我们需要遍历每个字符一次。
空间复杂度O(S)其中 S 为字符集大小在c中使用哈希映射最多只会存储 52 个即小写字母与大写字母的数量之和键值对。
8. 621 任务调度器 解法桶思想 先考虑最为简单的情况假设只有一类任务除了最后一个任务以外其余任务在安排后均需要增加 n 个单位的冻结时间。设这类任务的个数为max则需要构造max个桶每个桶最多保存n1个任务。 将任务数记为 m 个其中前m−1 个任务均要消耗n1 的单位时间最后一个任务仅消耗 1 个单位时间即所需要的时间为 (n1)×(m−1)1。 当存在多个任务时由于每一类任务都需要被完成因此本质上我们最需要考虑的是将数量最大的任务安排掉其他任务则是间插其中。 假设数量最大的任务数为 max共有 tot 个任务数为 max 的任务种类。 实际上当任务总数不超过 (n1)×(max−1)tot 注意tot就是最后一行的任务数时我们总能将其他任务插到空闲时间中去不会引入额外的冻结时间下左图而当任务数超过该值时我们可以在将其横向添加每个 n1 块的后面同时不会引入额外的冻结时间下右图 注意到左图中的任务所需的最短时间其实为 (n1)×(max−1)tot 而右图中的最短时间就是其task序列的长度本身若是超过了(n1)×(max−1)tot 那么其所需的时间就是task的长度。 因此我们需要返回的就是二者之中的最大值即可
代码
class Solution {
public:int leastInterval(vectorchar tasks, int n) {if(n0)return tasks.size();vectorintletterToCount(26);for(char c:tasks){letterToCount[c-A];}int maxCnt0,tot0;for(int i0;iletterToCount.size();i){maxCntstd::max(maxCnt,letterToCount[i]);}for(int i0;iletterToCount.size();i){if(letterToCount[i]maxCnt)tot;}int lentasks.size();return std::max((n1)*(maxCnt-1)tot,len);}
};时间复杂度O*(n*C)空间复杂度O©其中 C26 为任务字符集大小
9. 179 最大数 解法贪心自定义排序
对于 nums中的任意两个值 a 和 b我们无法直接从常规角度上确定其大小/先后关系。
但我们可以根据「结果」来决定 a和 b 的排序关系
如果拼接结果 ab 要比 ba好那么我们会认为 a应该放在 b 前面。
例如上面的示例2中30和3的大小比较我们认为330,原因是330303即ab的拼接结果比ba好。
算法流程 首先设置数组str将nums数组转为字符串 然后使用自定义排序定义排序规则为拼接后的字符串的大小比较 最后将数组str中的字符串转为输出的字符串 另外注意我们需要处理前导零最多保留一位。即如果最后的答案的第一位是‘0’就直接返回’0’
贪心算法的解法的正确性证明可见179. 最大数 - 力扣LeetCode
代码
class Solution {
public:string largestNumber(vectorint nums) {vectorstringstr;for(int i:nums){str.emplace_back(to_string(i));}sort(str.begin(),str.end(),[](const string left,const string right){return leftrightrightleft;});string result;for(auto c:str){resultc;}if(result[0]0){return 0;}return result;}
};时间复杂度On logn)
空间复杂度O(logn)
10. 56 合并区间 解法排序贪心
用数组res存储最终的答案。
首先我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 res 数组中并按顺序依次考虑之后的每个区间
如果当前区间的左端点在数组res 中最后一个区间的右端点之后那么它们不会重合我们可以直接将这个区间加入数组 merged 的末尾
否则它们重合我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点将其置为二者的较大值。
其正确性可见官方题解
56. 合并区间 - 力扣LeetCode
代码
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorintres;if(intervals.size()1)return intervals;sort(intervals.begin(),intervals.end());res.push_back(intervals[0]);for(int i1;iintervals.size();i){int leftres.back()[0];int rightres.back()[1];if(intervals[i][0]right){if(intervals[i][1]right){res.pop_back();res.push_back({left,intervals[i][1]});} }else{res.push_back(intervals[i]);}}return res;}
};时间复杂度O(nlogn)其中 n 为区间的数量。除去排序的开销我们只需要一次线性扫描所以主要的时间开销是排序的O(nlogn)。
空间复杂度O(logn)其中 n 为区间的数量。这里计算的是存储答案之外使用的额外空间。O(logn) 即为排序所需要的空间复杂度。
11. 57 插入区间 解法模拟区间合并一次遍历 对于区间 $S1[l_1,r_1] $和 S 2 [ l 2 , r 2 ] S_2 [l_2, r_2] S2[l2,r2]S如果它们之间没有重叠没有交集说明要么 S 1 S_1 S1在 S 2 S_2 S2的左侧此时有 r 1 l 2 r_1 l_2 r1l2要么 S 1 S_1 S1在 S 2 S_2 S2的右侧此时有 l 1 r 2 l_1 r_2 l1r2。 如果 r 1 l 2 r_1 l_2 r1l2和 l 1 r 2 l_1 r_2 l1r2二者均不满足说明 S 1 S_1 S1 和 S 2 S_2 S2 必定有交集它们的交集即为 [ max ( l 1 , l 2 ) , min ( r 1 , r 2 ) ] [\max(l_1, l_2), \min(r_1, r_2)] [max(l1,l2),min(r1,r2)],并集为 [ min ( l 1 , l 2 ) , max ( r 1 , r 2 ) ] [\min(l_1, l_2), \max(r_1, r_2)] [min(l1,l2),max(r1,r2)]
算法思路
在给定的区间集合 X \mathcal{X} X 互不重叠的前提下当我们需要插入一个新的区间 S [ left , right ] S [\textit{left}, \textit{right}] S[left,right]时我们只需要找出所有与区间 S 重叠的区间集合 X ′ \mathcal{X} X′,将 X ′ \mathcal{X} X′ 中的所有区间连带上区间 S 合并成一个大区间 最终的答案即为不与 X ′ \mathcal{X} X′ 重叠的区间以及合并后的大区间。 这样做的正确性在于给定的区间集合中任意两个区间都是没有交集的因此所有需要合并的区间就是所有与区间 S 重叠的区间。
并且在给定的区间集合已经按照左端点排序的前提下所有与区间 S 重叠的区间在数组 intervals \textit{intervals} intervals 中下标范围是连续的因此我们可以对所有的区间进行一次遍历就可以找到这个连续的下标范围。
当我们遍历到区间 [ l i , r i ] [l_i,r_i] [li,ri]时
如果 r i left r_i \textit{left} rileft说明 [ l i , r i ] [l_i,r_i] [li,ri] 与 S 不重叠并且在其左侧我们可以直接将 [ l i , r i ] [l_i,r_i] [li,ri]加入答案
如果 l i right l_i \textit{right} liright说明 [ l i , r i ] [l_i,r_i] [li,ri]与 S 不重叠并且在其右侧我们可以直接将 [ l i , r i ] [l_i,r_i] [li,ri]加入答案
如果上面两种情况均不满足说明 [ l i , r i ] [l_i,r_i] [li,ri]与 S 重叠我们无需将 [ l i , r i ] [l_i,r_i] [li,ri] 加入答案。此时我们需要将 S 与 [ l i , r i ] [l_i,r_i] [li,ri] 合并即将 S 更新为其与 [ l i , r i ] [l_i,r_i] [li,ri]的并集。
那么我们应当在什么时候将区间 S 加入答案呢由于我们需要保证答案也是按照左端点排序的因此当我们遇到第一个 满足 l i right l_i \textit{right} liright
的区间时说明以后遍历到的区间不会与 S 重叠并且它们左端点一定会大于 S 的左端点。此时我们就可以将 S 加入答案。特别地如果不存在这样的区间我们需要在遍历结束后将 S 加入答案。
代码
class Solution {
public:vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) {vectorvectorintres;int nintervals.size();bool isInsertfalse;int leftnewInterval[0];int rightnewInterval[1];for(int i0;in;i){if(intervals[i][1]left){res.push_back(intervals[i]);}else if(intervals[i][0]right){if(!isInsert){//找到了插入位置res.push_back({left,right});isInserttrue;}res.push_back(intervals[i]);}else{//有交集leftmin(left,intervals[i][0]);rightmax(right,intervals[i][1]);}}if(!isInsert){res.push_back({left,right});}return res;}
};时间复杂度O(n)其中 n 是数组 intervals 的长度即给定的区间个数。
空间复杂度O(1)。除了存储返回答案的空间以外我们只需要额外的常数空间即可。
13. 452 用最少数量的箭引爆气球 解法排序贪心
我们把气球看做区间箭还是箭箭是垂直向上射出。
首先对于右端点最小的那个区间如果想要用箭穿过它那么一定从它的右端点穿过从右端点穿过才只会穿过更多的区间。 接下来对于这只箭能未能穿过的区间再从中找出右端点最小的区间。对于这只箭未能穿过的区间如此往复的找下去。最终我们使用的箭数就是最少的。 如何寻找第一个右端点最小的区间以及在未被第一支箭穿过的剩余区间中继续寻找第一个右端点最小的区间呢
当我们把每个区间按照右端点升序排序后显然第一个区间就是我们最开始要找的第一个区间后序也可以进一步找到满足条件的最小右端点区间。具体的过程如下
首先将区间按照右端点升序排序此时位序为1的区间就是我们要找的第一个区间如图我们需要记录下第一个区间的右端点right射出第一支箭然后继续遍历此时就会存在两种情况
对于左端点小于等于right的区间说明该区间能被前面的箭right穿过。 对于接下来左端点大于right的区间说明前面这支箭无法穿过该区间即该区间就是未被箭穿过的区间集合的第一个区间我们又找到了第一个未被箭穿过的区间此时我们用一把新的箭穿过该区间的右端点即更新right points[i][1]并将使用的箭数1。如此往复。
代码
bool pointscmp(const vectorinta,const vectorintb){return a[1]b[1];
}
class Solution {
public:int findMinArrowShots(vectorvectorint points) {sort(points.begin(),points.end(),pointscmp);int result1;int arrowpoints[0][1];int npoints.size();for(int i1;in;i){if(points[i][0]arrow){continue;}arrowpoints[i][1];result;}return result;}
};时间复杂度O(nlogn)其中 nn是数组 points 的长度。排序的时间复杂度为 O(nlogn)对所有气球进行遍历并计算答案的时间复杂度为 O(n)其在渐进意义下小于前者因此可以忽略。
空间复杂度O(logn)即为排序需要使用的栈空间。
14. 435 无重叠区间 解法一排序贪心
关于为什么是按照区间右端点排序 官解里对这个描述的非常清楚了这个题其实是预定会议的一个问题给你若干时间的会议然后去预定会议那么能够预定的最大的会议数量是多少核心在于我们要找到最大不重叠区间的个数。 如果我们把本题的区间看成是会议那么按照右端点排序我们一定能够找到一个最先结束的会议而这个会议一定是我们需要添加到最终结果的的首个会议。这个不难贪心得到因为这样能够给后面预留的时间更长。
关于为什么是不能按照区间左端点排序 这里补充一下为什么不能按照区间左端点排序。同样地我们把本题的区间看成是会议如果“按照左端点排序我们一定能够找到一个最先开始的会议”但是最先开始的会议不一定最先结束。。举个例子 区间a是最先开始的如果我们采用区间a作为放入最大不重叠区间的首个区间那么后面我们只能采用区间d作为第二个放入最大不重叠区间的区间但这样的话最大不重叠区间的数量为2。但是如果我们采用区间b作为放入最大不重叠区间的首个区间那么最大不重叠区间的数量为3因为区间b是最先结束的。
代码
class Solution {
public:
int eraseOverlapIntervals(vectorvectorint intervals) {if(intervals.size()1||intervals.size()0)return 0;sort(intervals.begin(),intervals.end(),[](const auto u,const auto v){return u[1]v[1];});int nintervals.size();int rightintervals[0][1];int ans1;for(int i1;in;i){if(intervals[i][0]right){ans;rightintervals[i][1];}}return n-ans;}
};时间复杂度O(nlogn)其中 n 是区间的数量。我们需要 O(nlogn) 的时间对所有的区间按照右端点进行升序排序并且需要O(n) 的时间进行遍历。由于前者在渐进意义下大于后者因此总时间复杂度为O(nlogn)。
空间复杂度O(logn)即为排序需要使用的栈空间。
解法二动态规划
见官方题解此解法的时间复杂度过高会超出时间限制
435. 无重叠区间 - 力扣LeetCode
15. 646 最长数对链 解法一排序贪心
这题解法和435无重叠区间基本相同仅仅是判断条件不同无重叠子区间要求边界点可以重叠如[1,2]和[2,3]但是646要求边界点不重叠
代码
class Solution {
public:int findLongestChain(vectorvectorint pairs) {if(pairs.size()1)return 1;sort(pairs.begin(),pairs.end(),[](const auto u,const auto v){return u[1]v[1];});int npairs.size();int ans1;int right0;for(int i1;in;i){if(pairs[i][0]pairs[right][1]){ans;righti;}}return ans;}
};时间复杂度O(nlogn)其中 n 为 pairs 的长度。排序的时间复杂度为 O(nlogn)。
空间复杂度O(logn)为排序的空间复杂度。
解法二动态规划
定义 dp[i] 为以 pairs[i] 为结尾的最长数对链的长度。计算 dp[i] 时可以先找出所有的满足 pairs [ i ] [ 0 ] pairs [ j ] [ 1 ] \textit{pairs}[i][0] \textit{pairs}[j][1] pairs[i][0]pairs[j][1]的 j并求出最大的 dp[j]的值即可赋为这个最大值加一。这种动态规划的思路要求计算dp[i] 时所有潜在的 dp[j] 已经计算完成可以先将 pairs 进行排序来满足这一要求。初始化时dp 需要全部赋值为 1。
代码
class Solution {
public:int findLongestChain(vectorvectorint pairs) {int npairs.size();vectorintdp(n,1);sort(pairs.begin(),pairs.end());for(int i0;in;i)for(int j0;ji;j){if(pairs[i][0]pairs[j][1]){dp[i]max(dp[i],dp[j]1);}}return dp[n-1];}
};时间复杂度O(n^2)其中 n 为 pairs 的长度。排序的时间复杂度为 O(nlogn)两层 for 循环的时间复杂度为 O(n^2)
空间复杂度O(n)数组 dp 的空间复杂度为 O(n)。
解法三最长上升子序列
解法二实际上是最长递增子序列的动态规划解法这个解法可以改造为贪心 二分查找的形式。用一个数组arr 来记录当前最优情况arr[i]就表示长度为 i1i 的数对链的末尾可以取得的最小值遇到一个新数对时先用二分查找得到这个数对可以放置的位置再更新 arr。
注意由于是最长上升子序列如果新数(left)大于arr末尾的值(right)则直接加入否则就在arr中找到left所在的位置判断此时对应的right和arr中记录的right哪个更小取更小的值
代码
class Solution {
public:int findLongestChain(vectorvectorint pairs) {sort(pairs.begin(),pairs.end());vectorintarr;for(auto p:pairs){int leftp[0];int rightp[1];if(arr.empty()||leftarr.back())arr.push_back(right);else{int idxlower_bound(arr.begin(),arr.end(),left)-arr.begin();arr[idx]min(arr[idx],right);}}return arr.size();}
};时间复杂度O(nlogn)其中 n 为 pairs 的长度。排序的时间复杂度为 O(nlogn)二分查找的时间复杂度为 O(nlogn)二分的次数为 O(n)。
空间复杂度O(n)数组 arr 的长度最多为 O(n)。
16. 406 按照身高重建队列 解法排序贪心
题目描述整数对 (h, k) 表示其中 h 是这个人的身高k 是排在这个人前面且身高大于或等于 h 的人数。 一般这种数对还涉及排序的根据第一个元素正向排序根据第二个元素反向排序或者根据第一个元素反向排序根据第二个元素正向排序往往能够简化解题过程。 在本题目中我首先对数对进行排序按照数对的元素 1 降序排序按照数对的元素 2 升序排序。
原因是按照元素 1 进行降序排序对于每个元素在其之前的元素的个数就是大于等于他的元素的数量而按照第二个元素正向排序我们希望 k 大的尽量在后面减少插入操作的次数。
算法步骤
排序按照元素1降序排序元素2升序排序创建空数组result表示结果遍历people[i]若是元素2的值等于result的长度或者result为空直接在尾部插入peple[i],否则则在元素2的位置插入people[i]
代码
class Solution {
public:vectorvectorint reconstructQueue(vectorvectorint people) {vectorvectorintresult; sort(people.begin(),people.end(),[](const auto u,const auto v){if(u[0]!v[0])return u[0]v[0];elsereturn u[1]v[1];});int npeople.size();for(int i0;in;i){int speople[i][1];if(result.size()people[i][1]||result.empty()){result.emplace_back(people[i]);}else{result.insert(result.begin()s,people[i]);}}return result;}
};时间复杂度O(n^2)其中 n 是数组 people 的长度。我们需要 )O(nlogn) 的时间进行排序随后需要 O(n^2) 的时间遍历每一个人并将他们放入队列中。由于前者在渐近意义下小于后者因此总时间复杂度为 O(n^2)。
空间复杂度O(logn)。
17. 48 旋转图像 解法一递推公式分组旋转
首先我们由示例2可以观察到如下图所示矩阵顺时针旋转 90º 后可找到以下规律 「第 i 行」元素旋转到「第 n−1−i列」元素 「第 j列」元素旋转到「第 j 行」元素
因此对于矩阵任意第 i行、第 j 列元素 m a t r i x [ i ] [ j ] matrix[i][j] matrix[i][j] 矩阵旋转 90º 后「元素位置旋转公式」为 m a t r i x [ i ] [ j ] → m a t r i x [ j ] [ n − 1 − i ] \begin{aligned} matrix[i][j] \rightarrow matrix[j][n - 1 - i]\end{aligned} matrix[i][j]→matrix[j][n−1−i] 原索引位置 → 旋转后索引位置 \begin{aligned}原索引位置 \rightarrow 旋转后索引位置 \end{aligned} 原索引位置→旋转后索引位置
以位于矩阵四个角点的元素为例设矩阵左上角元素 A 、右上角元素 B 、右下角元素 C 、左下角元素 D 。矩阵旋转 90º 后相当于依次先后执行 D→A , C→D , B→C, A→B修改元素即如下「首尾相接」的元素旋转操作 如上图所示由于第 1 步 D→A 已经将 A覆盖导致 A丢失此丢失导致最后第 A→B 无法赋值。为解决此问题考虑借助一个「辅助变量 tmp预先存储 A 此时的旋转操作变为
暂存 tmpA A←D←C←B←tmp 如上图所示一轮可以完成矩阵 4 个元素的旋转。因而只要分别以矩阵左上角 1/41/41/4 的各元素为起始点执行以上旋转操作即可完整实现矩阵旋转。
具体来看当矩阵大小 n 为偶数时取前 n 2 \frac{n}{2} 2n 行、前 $\frac{n}{2} $列的元素为起始点当矩阵大小 n 为奇数时取前 $\frac{n}{2} $行、前 $\frac{n 1}{2} $ 列的元素为起始点。
令 m a t r i x [ i ] [ j ] A matrix[i][j]A matrix[i][j]A根据文章开头的元素旋转公式可推导得适用于任意起始点的元素旋转操作
暂存 t m p m a t r i x [ i [ j ] tmpmatrix[i[j] tmpmatrix[i[j] m a t r i x [ i [ j ] ← m a t r i x [ n − 1 − j ] [ i ] ← m a t r i x [ n − 1 − i ] [ n − 1 − j ] ← m a t r i x [ j ] [ n − 1 − i ] ← t m p matrix[i[j] \leftarrow matrix[n - 1 - j][i] \leftarrow matrix[n - 1 - i][n - 1 - j] \leftarrow matrix[j][n - 1 - i] \leftarrow tmp matrix[i[j]←matrix[n−1−j][i]←matrix[n−1−i][n−1−j]←matrix[j][n−1−i]←tmp
代码
class Solution {
public:void rotate(vectorvectorint matrix) {int nmatrix.size();for(int i0;in/2;i)for(int j0;j(n1)/2;j){int tmpmatrix[i][j];matrix[i][j]matrix[n-1-j][i];matrix[n-1-j][i]matrix[n-1-i][n-1-j];matrix[n-1-i][n-1-j]matrix[j][n-1-i];matrix[j][n-1-i]tmp;}}
};时间复杂度 O(N^2) 其中 N 为输入矩阵的行列数。需要将矩阵中每个元素旋转到新的位置即对矩阵所有元素操作一次使用 O(N^2)时间。 空间复杂度 O(1) 临时变量 tmp 使用常数大小的额外空间。值得注意当循环中进入下轮迭代上轮迭代初始化的 tmp 占用的内存就会被自动释放因此无累计使用空间。
解法二用翻转代替旋转
见官方题解48. 旋转图像 - 力扣LeetCode 代码
class Solution {
public:void rotate(vectorvectorint matrix) {int nmatrix.size();//水平翻转for(int i0;in/2;i){for(int j0;jn;j){swap(matrix[i][j],matrix[n-1-i][j]);}}//主对角线翻转for(int i0;in;i){for(int j0;ji;j){swap(matrix[i][j],matrix[j][i]);}}}
};时间复杂度O(N^2)其中 N 是 matrix 的边长。对于每一次翻转操作我们都需要枚举矩阵中一半的元素。
空间复杂度O(1)。为原地翻转得到的原地旋转。
18. 169 多数元素 解法一哈希表
使用hash表存储每个元素的数量如果大于n/2则返回因为题目应该多数元素之存在一个
代码
class Solution {
public:int majorityElement(vectorint nums) {unordered_mapint,intnumToSize;for(auto n:nums){numToSize[n];if(numToSize[n]nums.size()/2){return n;}}return 0;}
};时间复杂度O(n)
空间复杂度O(n)
解法二Boyer-Moore 算法【实现O(1)的空间复杂度】
见官方题解
代码
class Solution {
public:int majorityElement(vectorint nums) {int candidate-1;int count0;for(int num:nums){if(numcandidate)count;else if(--count0){candidatenum;count1;}}return candidate;}
};时间复杂度:O(n)
空间复杂度:O(1)
解法排序法、分治法、随机化、可见官方题解
169. 多数元素 - 力扣LeetCode
19. 215 数组中的第k个最大元素 解法改进版的快排
我们可以用快速排序来解决这个问题先对原数组排序再返回倒数第 kkk 个位置这样平均时间复杂度是 O(nlogn)O(n \log n)O(nlogn)但其实我们可以做的更快。
首先我们来回顾一下快速排序这是一个典型的分治算法。我们对数组 a[l⋯r] 做快速排序的过程是参考《算法导论》
分解 将数组 a[l⋯r]「划分」成两个子数组 a[l⋯q−1]、a[q1⋯r]使得 a[l⋯q−1] 中的每个元素小于等于 a[q]且 a[q] 小于等于 a[q1⋯r] 中的每个元素。其中计算下标 q 也是「划分」过程的一部分。 解决 通过递归调用快速排序对子数组 a[l⋯q−1]和 a[q1⋯r]进行排序。 合并 因为子数组都是原址排序的所以不需要进行合并操作a[l⋯r]已经有序。 上文中提到的 「划分」 过程是从子数组 a[l⋯r]中选择任意一个元素 x作为主元调整子数组的元素使得左边的元素都小于等于它右边的元素都大于等于它 x 的最终位置就是 q。 由此可以发现每次经过「划分」操作后我们一定可以确定一个元素的最终位置即 x的最终位置为 q并且保证 a[l⋯q−1]中的每个元素小于等于 a[q]且 a[q] 小于等于 a[q1⋯r]中的每个元素。所以只要某次划分的 q 为第 k-1 个下标的时候我们就已经找到了答案。 我们只关心这一点至于 a[l⋯q−1]和 a[q1⋯r]是否是有序的我们不关心。
因此我们可以改进快速排序算法来解决这个问题在分解的过程当中我们会对子数组进行划分如果划分得到的 q 正好就是我们需要的下标就直接返回 a[q]否则如果 q 比目标下标大就递归左子区间否则递归右子区间。这样就可以把原来递归两个区间变成只递归一个区间提高了时间效率。这就是「快速选择」算法。
我们知道快速排序的性能和「划分」出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n−1每次递归的时候又向 n−1的集合中递归这种情况是最坏的时间代价是 O(n ^ 2)。我们可以引入随机化来加速这个过程它的时间代价的期望是 O(n)证明过程可以参考「《算法导论》9.2期望为线性的选择算法」。需要注意的是这个时间复杂度只有在 随机数据 下才成立而对于精心构造的数据则可能表现不佳。因此我们这里并没有真正地使用随机数而是使用双指针的方法这种方法能够较好地应对各种数据。 注意我最初使用填坑法来实现快排的时候基准值选择的是最左边的值这样对有非常多的重复元素的情况下超时如示例40 代码
class Solution {
public:int quickSelect(vectorintnums,int left,int right,int k){int pivotIndex left std::rand() % (right - left 1); // 随机选择枢轴int pivotValue nums[pivotIndex];std::swap(nums[pivotIndex], nums[left]); int ileft,jright;while(ij){while(ijnums[j]pivotValue)j--;nums[i]nums[j];while(ijnums[i]pivotValue)i;nums[j]nums[i];}nums[i]pivotValue;if(ik-1)return nums[i];else if(ik-1) return quickSelect(nums,i1,right,k);else return quickSelect(nums,left,i-1,k);}int findKthLargest(vectorint nums, int k) {return quickSelect(nums,0,nums.size()-1,k);}
};时间复杂度:O(n)
空间复杂度O(logn)递归使用栈空间的空间代价的期望为 O(logn)。
解法二小根堆
c的stl库中的priority_queue可以实现小根队
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint,vectorint,greaterintque;for(auto n:nums){que.push(n);if(que.size()k){que.pop();}}return que.top();}
};时间复杂度O(nlogn)
空间复杂度O(n)
20. 75 颜色分类 一开始看到这道题想的是直接一个调用STL库的sort函数一步到位但是这明显不是面试官想要的
解法一单指针–交换排序
我们可以考虑对数组进行两次遍历。在第一次遍历中我们将数组中所有的 0 交换到数组的头部。在第二次遍历中我们将数组中所有的 1 交换到头部的 0之后。此时所有的 2 都出现在数组的尾部这样我们就完成了排序。
具体地我们使用一个指针 ptr 表示当前「头部」指向的位置初始化的时候ptr指向0的位置。
在第一次遍历中我们从左向右遍历整个数组如果找到了 0那么就需要将 0 与ptr位置的元素进行交换并将ptr指针向后移动一位。在遍历结束之后所有的 0 都被交换到「头部」的范围并且「头部」只包含 0此时ptr指针指向所有的0之后的位置。
在第二次遍历中我们从当前的ptr开始遍历整个数组如果找到了 1那么就需要将 1 与ptr位置的元素进行交换并将ptr指针向后移动一位。在遍历结束之后所有的 1都被交换到「头部」的范围并且都在 0 之后此时 2 只出现在「头部」之外的位置因此排序完成。
代码
class Solution {
public:void sortColors(vectorint nums) {int nnums.size();int ptr0;for(int i0;in;i){if(nums[i]0){swap(nums[i],nums[ptr]);ptr;}}for(int iptr;in;i){if(nums[i]1){swap(nums[i],nums[ptr]);ptr;}}}
};时间复杂度O(n)其中 n是数组 nums的长度。空间复杂度O(1)。
解法二双指针【最快】
p0指针用于替换0p2指针用于替换2
考虑使用指针 p0来交换 0p2来交换 2。此时p0 的初始值仍然为 0而 p2的初始值为 n−1。在遍历的过程中我们需要找出所有的 0 交换至数组的头部并且找出所有的 2 交换至数组的尾部。因此p0指针初始化时候指向数组的第一个元素p2指针初始化时候指向数组的尾部
由于此时其中一个指针 p2是从右向左移动的因此当我们在从左向右遍历整个数组时如果遍历到的位置超过了 p2 那么就可以直接停止遍历了。
具体地我们从左向右遍历整个数组设当前遍历到的位置为 i对应的元素为 nums[i]如果找到了 0将其与 nums[p0] 进行交换并将 p0 向后移动一个位置
如果找到了 2那么将其与 nums[p2]进行交换并将 p2向前移动一个位置。 注意找到2的位置后与nums[p2]进行交换容易出错对于第二种情况当我们将 nums[i]与 nums[p2 进行交换之后新的 nums[i]可能仍然是 2也可能是 0。然而此时我们已经结束了交换开始遍历下一个元素 nums[i1]不会再考虑 nums[i]了这样我们就会得到错误的答案。 因此当我们找到 2 时我们需要不断地将其与 nums[p2] 进行交换直到新的 nums[i]不为 2。此时如果 nums[i] 为 0那么对应着第一种情况如果 nums[i] 为 1那么就不需要进行任何后续的操作。 代码
class Solution {
public:void sortColors(vectorint nums) {int nnums.size();int p00,p2n-1;for(int i0;ip2;i){while(ip2nums[i]2){swap(nums[i],nums[p2]);--p2;}if(nums[i]0){swap(nums[i],nums[p0]);p0;}}}
};时间复杂度O(n)其中 nnn 是数组 nums* 的长度。空间复杂度O(1)。
解法三双指针同时找到0和1的位置见官方题解75. 颜色分类 - 力扣LeetCode
21. 324 摆动顺序II 解法一排序双指针
先将数组进行排序然后再通过双指针逐个插入我们将排序好的元素分成两部分左半部分是较小的元素右半部分是较大元素然后用两个指针都指向两部分的右侧采用先插入left指针指向的元素再插入right指针指向的元素来达到摇摆的目的一小一大。 代码
class Solution {
public:void wiggleSort(vectorint nums) {vectorintarr(nums);sort(arr.begin(),arr.end());int left(nums.size()-1)/2,rightnums.size()-1;for(int i0;inums.size();i){if(i%20){nums[i]arr[left];left--;}else{nums[i]arr[right];right--;}}}
};时间复杂度O(nlogn)排序所需的时间复杂度是O(nlogn)插入O(n)整体O(nlogn) 空间复杂度O(n)需要额外的空间存放排序的元素。
方法二三向切分见官方题解
方法三索引转换
方法四递归优化
见官方题解
324. 摆动排序 II - 力扣LeetCode
22. 517 超级洗衣机[未解] 解法贪心
见官方题解517. 超级洗衣机 - 力扣LeetCode
class Solution {
public:int findMinMoves(vectorint machines) {int totaccumulate(machines.begin(),machines.end(),0);int nmachines.size();if(tot%n){return -1;}int avgtot/n;int ans0,sum0;for(int num:machines){num-avg;sumnum;ansmax(ans,max(abs(sum),num));}return ans;}
};时间复杂度O(n)其中 n 是数组machines 的长度。
空间复杂度O(1)。只需要常数的空间存放若干变量。
23. 649 Dota2 参议院 解法贪心循环队列
思路与算法
我们以天辉方的议员为例。当一名天辉方的议员行使权利时
如果目前所有的议员都为天辉方那么该议员可以直接宣布天辉方取得胜利
如果目前仍然有夜魇方的议员那么这名天辉方的议员只能行使「禁止一名参议员的权利」这一项权利。显然该议员不会令一名同为天辉方的议员丧失权利所以他一定会挑选一名夜魇方的议员。那么应该挑选哪一名议员呢**容易想到的是应该贪心地挑选按照投票顺序的下一名夜魇方的议员。这也是很容易形象化地证明的既然只能挑选一名夜魇方的议员那么就应该挑最早可以进行投票的那一名议员如果挑选了其他较晚投票的议员那么等到最早可以进行投票的那一名议员行使权利时一名天辉方议员就会丧失权利这样就得不偿失了。**
由于我们总要挑选投票顺序最早的议员因此我们可以使用两个队列 radiant 和 dire 分别按照投票顺序存储天辉方和夜魇方每一名议员的投票时间。随后我们就可以开始模拟整个投票的过程
如果此时 radiant 或者 dire 为空那么就可以宣布另一方获得胜利
如果均不为空那么比较这两个队列的首元素就可以确定当前行使权利的是哪一名议员。如果radiant 的首元素较小那说明轮到天辉方的议员行使权利其会挑选 dire 的首元素对应的那一名议员。因此我们会将 dire 的首元素永久地弹出并将radiant 的首元素弹出增加 n 之后再重新放回队列这里 n 是给定的字符串senate 的长度即表示该议员会参与下一轮的投票。
同理如果 dire 的首元素较小那么会永久弹出 radiant 的首元素剩余的处理方法也是类似的。
这样一来我们就模拟了整个投票的过程也就可以得到最终的答案了。
class Solution {
public:string predictPartyVictory(string senate) {queueintradiant,dire;int nsenate.size();for(int i0;in;i){if(senate[i]R)radiant.push(i);elsedire.push(i);}while(!radiant.empty()!dire.empty()){if(radiant.front()dire.front()){radiant.push(radiant.front()n);radiant.pop();dire.pop();}else{dire.push(dire.front()n);dire.pop();radiant.pop();}}return !radiant.empty()?Radiant:Dire;}
};时间复杂度O(n)其中 n 是字符串 senate 的长度。在模拟整个投票过程的每一步我们进行的操作的时间复杂度均为 O(1)并且会弹出一名天辉方或夜魇方的议员。由于议员的数量为 n因此模拟的步数不会超过 n时间复杂度即为 O(n)。
空间复杂度O(n)即为两个队列需要使用的空间。
24. 678 有效的括号字符串 解法一双栈
首先取得两个栈st1,st2,st1存放的是左括号的索引st2存放的是右括号的索引遍历字符串数组如果是左括号则入栈st1如果是星号则入栈st2;如果是右括号优先将st1中的左括号弹出与右括号匹配;如果左括号栈为空的条件下会弹出星号栈的星号作为匹配的左括号最后左括号栈和星号栈可能不为空那么则检验左括号栈中与星号栈是否可以匹配注意到此时星号栈的索引号必须大于左括号栈才能使得左括号和星号匹配
代码
class Solution {
public:bool checkValidString(string s) {stackintst1;//(栈stackintst2;//* 栈for(int i0;is.size();i){if(s[i]()st1.push(i);else if(s[i]*)st2.push(i);else{if(!st1.empty()){st1.pop();}else if(!st2.empty()){st2.pop();}elsereturn false;}}if(st1.empty())return true;else{//注意左括下标必须小于星号下标while(!st1.empty()){if(!st2.empty()st1.top()st2.top()){st1.pop();st2.pop();}else{return false;}}return true;}}
};解法二动态规划
见官方题解678. 有效的括号字符串 - 力扣LeetCode
要判断 s 是否为有效的括号字符串需要判断 s 的首尾字符以及 s 的中间字符是否符合有效的括号字符串的要求。可以使用动态规划求解。
假设字符串 s 的长度为 n。定义$\textit{dp}[i][j] $表示字符串 s 从下标 i 到 j 的子串是否为有效的括号字符串其中 0≤i≤jn。
动态规划的边界情况是子串的长度为 1或 2 的情况。
当子串的长度为 1 时只有当该字符是 ‘*’ 时才是有效的括号字符串此时子串可以看成空字符串
当子串的长度为 2 时只有当两个字符是 “() , “(* , “*) , “** \text{()}, \text{(*}, \text{*)}, \text{**} “(),“(*,“*),“** 中的一种情况时才是有效的括号字符串此时子串可以看成 $\text{()} $。
当子串的长度大于 2 时需要根据子串的首尾字符以及中间的字符判断子串是否为有效的括号字符串。字符串 s 从下标 i到 j 的子串的长度大于 2 等价于 j−i≥2此时 dp [ i ] [ j ] \textit{dp}[i][j] dp[i][j]的计算如下只要满足以下一个条件就有 dp [ i ] [ j ] true \textit{dp}[i][j] \text{true} dp[i][j]true
如果 s[i] 和 s[j] 分别为左括号和右括号或者为 ‘*’则当 dp [ i 1 ] [ j − 1 ] true \textit{dp}[i 1][j - 1] \text{true} dp[i1][j−1]true 时 dp [ i ] [ j ] true \textit{dp}[i][j] \text{true} dp[i][j]true此时 s[i]和 s[j] 可以分别看成左括号和右括号
如果存在 i≤kj 使得 dp [ i ] [ k ] \textit{dp}[i][k] dp[i][k]和 dp [ k 1 ] [ j ] \textit{dp}[k 1][j] dp[k1][j]都为 true则 dp [ i ] [ j ] true \textit{dp}[i][j] \text{true} dp[i][j]true因为字符串 s的下标范围[i,k] 和 [k1,j] 的子串分别为有效的括号字符串将两个子串拼接之后的子串也为有效的括号字符串对应下标范围 [i,j]。
上述计算过程为从较短的子串的结果得到较长的子串的结果因此需要注意动态规划的计算顺序。最终答案为 dp [ 0 ] [ n − 1 ] \textit{dp}[0][n - 1] dp[0][n−1]。
代码
class Solution {
public:bool checkValidString(string s) {int ns.size();vectorvectorbooldp(n,vectorbool(n,false));for(int i0;in;i){if(s[i]*){dp[i][i]true;}}for(int i1;in;i){char c1s[i-1];char c2s[i];if((c1(c2))||(c1(c2*)||(c1*c2))||(c1*c2*))dp[i-1][i]true;}for(int in-3;i0;i--){char c1s[i];for(int ji2;jn;j){char c2s[j];if((c1(||c1*)(c2)||c2*)){dp[i][j]dp[i1][j-1];}for(int ki;kj!dp[i][j];k){dp[i][j]dp[i][k]dp[k1][j];}}}return dp[0][n-1];}
};时间复杂度O(n3)其中 n是字符串 s 的长度。动态规划的状态数是 O(n2)每个状态的计算时间最多为 O(n)。
空间复杂度O(n2)其中 n 是字符串 s 的长度。创建了 n 行 n 列的二维数组 dp
解法三贪心
见官方题解678. 有效的括号字符串 - 力扣LeetCode
使用贪心的思想可以将空间复杂度降到 O(1)。
从左到右遍历字符串遍历过程中未匹配的左括号数量可能会出现如下变化
如果遇到左括号则未匹配的左括号数量加 1
如果遇到右括号则需要有一个左括号和右括号匹配因此未匹配的左括号数量减 1
如果遇到星号由于星号可以看成左括号、右括号或空字符串因此未匹配的左括号数量可能加 1、减 1 或不变。
基于上述结论可以在遍历过程中维护未匹配的左括号数量可能的最小值和最大值根据遍历到的字符更新最小值和最大值
如果遇到左括号则将最小值和最大值分别加 1
如果遇到右括号则将最小值和最大值分别减 1
如果遇到星号则将最小值减 1将最大值加 1。
任何情况下未匹配的左括号数量必须非负因此当最大值变成负数时说明没有左括号可以和右括号匹配返回 false。
当最小值为 0 时不应将最小值继续减少以确保最小值非负。
遍历结束时所有的左括号都应和右括号匹配因此只有当最小值为 0 时字符串 s 才是有效的括号字符串。
class Solution {
public:bool checkValidString(string s) {int minCount0,maxCount0;//记录未匹配的左括号的个数的最小值和最大值int ns.size();for(int i0;in;i){char cs[i];if(c(){minCount;maxCount;}else if(c)){maxCount--;minCountmax(minCount-1,0);if(maxCount0){return false;}}else{maxCount;minCountmax(minCount-1,0);}}return minCount0;}
};时间复杂度O(n)其中 n 是字符串 s 的长度。需要遍历字符串一次。空间复杂度O(1)。
25. 420 强密码检验器 解法这道题比较麻烦的模拟并且没什么意义 解法见官方题解420. 强密码检验器 - 力扣LeetCode
代码
class Solution {
public:int strongPasswordChecker(string password) {int n password.size();bool has_lower false, has_upper false, has_digit false;for (char ch: password) {if (islower(ch)) {has_lower true;}else if (isupper(ch)) {has_upper true;}else if (isdigit(ch)) {has_digit true;}}int categories has_lower has_upper has_digit;if (n 6) {return max(6 - n, 3 - categories);}else if (n 20) {int replace 0;int cnt 0;char cur #;for (char ch: password) {if (ch cur) {cnt;}else {replace cnt / 3;cnt 1;cur ch;}}replace cnt / 3;return max(replace, 3 - categories);}else {// 替换次数和删除次数int replace 0, remove n - 20;// k mod 3 1 的组数即删除 2 个字符可以减少 1 次替换操作int rm2 0;int cnt 0;char cur #;for (char ch: password) {if (ch cur) {cnt;}else {if (remove 0 cnt 3) {if (cnt % 3 0) {// 如果是 k % 3 0 的组那么优先删除 1 个字符减少 1 次替换操作--remove;--replace;}else if (cnt % 3 1) {// 如果是 k % 3 1 的组那么存下来备用rm2;}// k % 3 2 的组无需显式考虑}replace cnt / 3;cnt 1;cur ch;}}if (remove 0 cnt 3) {if (cnt % 3 0) {--remove;--replace;}else if (cnt % 3 1) {rm2;}}replace cnt / 3;// 使用 k % 3 1 的组的数量由剩余的替换次数、组数和剩余的删除次数共同决定int use2 min({replace, rm2, remove / 2});replace - use2;remove - use2 * 2;// 由于每有一次替换次数就一定有 3 个连续相同的字符k / 3 决定因此这里可以直接计算出使用 k % 3 2 的组的数量int use3 min({replace, remove / 3});replace - use3;remove - use3 * 3;return (n - 20) max(replace, 3 - categories);}}
};
时间复杂度O(n)空间复杂度O(1)
26. 53 最大子数组和 解法一动态规划【步骤】
定义dp[i]表示数组中前i1注意这里的i是从0开始的个元素构成的连续子数组的最大和。如果要计算前i1个元素构成的连续子数组的最大和也就是计算dp[i]只需要判断dp[i-1]num[i]和num[i]哪个大如果dp[i-1]num[i]大则dp[i]dp[i-1]num[i]否则令dp[i]nums[i]。在递推过程中可以设置一个值max用来保存子序列的最大值最后返回即可。转移方程dp[i]Math.max(nums[i], nums[i]dp[i-1])边界条件判断当i等于0的时候也就是前1个元素他能构成的最大和也就是他自己所以dp[0]num[0];
代码
class Solution {
public:int maxSubArray(vectorint nums) {int resnums[0];int nnums.size();vectorintdp(nums);for(int i1;in;i){dp[i]max(dp[i],dp[i-1]nums[i]);resmax(res,dp[i]);}return res;}
};时间复杂度O(n)其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。 空间复杂度O(1)。我们只需要常数空间存放若干变量。
解法二分治法
分治法的思路是这样的其实也是分类讨论。
连续子序列的最大和主要由这三部分子区间里元素的最大和得到
第 1 部分子区间 [left, mid] 第 2 部分子区间 [mid 1, right] 第 3 部分包含子区间 [mid , mid 1] 的子区间即 nums[mid] 与 nums[mid 1] 一定会被选取。 对这三个部分求最大值即可。
说明考虑第 3 部分跨越两个区间的连续子数组的时候由于 nums[mid] 与 nums[mid 1] 一定会被选取可以从中间向两边扩散扩散到底 选出最大值。 代码
class Solution {
public:int maxSubArray(vectorint nums) {int lennums.size();if(len0)return 0;return maxSubArraySum(nums,0,len-1);}int maxCrossingSum(vectorint nums,int left,int mid,int right){//一定包含nums[mid]元素int sum0;int leftSum-1e6;//左半边包含nums[mid]元素最多可以到达的地方for(int imid;ileft;i--){sumnums[i];if(sumleftSum){leftSumsum;}}sum0;int rightsum-1e6;for(int imid1;iright;i){sumnums[i];if(sumrightsum){rightsumsum;}}return leftSumrightsum;}int maxSubArraySum(vectorint nums,int left,int right){if(leftright)return nums[left];int midleft(right-left)/2;return max3(maxSubArraySum(nums,left,mid),maxSubArraySum(nums,mid1,right),maxCrossingSum(nums,left,mid,right));}int max3(int num1,int num2,int num3){return max(num1,max(num2,num3));}};时间复杂度O(NlogN)这里递归的深度是对数级别的每一层需要遍历一遍数组或者数组的一半、四分之一 空间复杂度O(logN)需要常数个变量用于选取最大值需要使用的空间取决于递归栈的深度.
27. 134 加油站 解法贪心一次遍历
最容易想到的解法就是一次遍历从头到尾遍历每个加油站并检查该加油站为起点最终能否行驶一周。我们可以通过减少被检查的加油站数目来降低总的时间复杂度。
即假设从x开始行驶无法到达y的下一站那么[x,y]的中间某一点为起始点也肯定无法到达y的下一站官方题解中包含详细证明
134. 加油站 - 力扣LeetCode
直观的理解如果能从x到达y的话那么从x到达(x,y)中间任何一站时剩余的油量肯定都是0的否则便无法一直到达y。
举例从a出发经过b到达c油量不够无法到达d。从a到达b的时候剩余油量最坏的情况也是0而如果直接从b出发初始油量只能0。从a出发在到达b点的时候油量还能0无法到达d点而如果直接从b点出发此时初始油量0就更不可能到达d点了。
因此在一次遍历起始点的时候假如x为起始点遍历到y时无法到达y的下一个节点那么下次遍历的起点就可以改为y1
代码
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int i0;int ngas.size();while(in){int sumGas0,sumCost0;int cnt0;while(cntn){int j(icnt)%n;sumGasgas[j];sumCostcost[j];if(sumCostsumGas){break;}cnt;}if(cntn){return i;}elseiicnt1;}return -1;}
};时间复杂度O(N)其中 N 为数组的长度。我们对数组进行了单次遍历。空间复杂度O(1)。
28. 581 最短无序连续子数组 解法一贪心双指针一次遍历 我们把整个数组分成三段处理。 起始时先通过双指针 left 和 right 找到左右两次侧满足 单调递增 的分割点。 即从left从左到右遍历找到nums[left]nums[left1]的索引left从right从右向左遍历找到nums[right]nums[right-1]的索引right即此时 [0,left] 和 [right,n) 满足升序要求而中间部分 (left,right) 不确保有序。 然后我们对中间部分 [left,right] 进行遍历 因为我们知道要使得中间部分排序后整体升序的话要保证中间部分的所有数都大于nums[left-1]【即第一块升序部分】中间部分的所有数要小于nums[right1]【即第三块的升序部分】 遍历中间部分若发现 nums[x]nums[left−1]由于对 [left,right] 部分进行排序后 nums[x] 会出现在 nums[left−1] 后将不满足整体升序此时我们需要调整分割点 left 的位置即向前移动直到nums[x]小于此时的nums[left-1]; 若发现 nums[x]nums[right1]由于对[left,right] 部分进行排序后 nums[x 会出现在 nums[right1]前将不满足整体升序此时我们需要调整分割点 right 的位置。
代码
class Solution {
public:int MIN-1e5,MAX1e5;int findUnsortedSubarray(vectorint nums) {int left0;int rightnums.size()-1;while(leftnums.size()-1){if(nums[left]nums[left1]){break;}left;}if(leftnums.size()-1)return 0;while(right0){if(nums[right]nums[right-1]){break;}right--;}int lleft,rright;//继续调整中间情况for(int il;ir;i){while(left1nums[i]nums[left-1])left--;while(rightnums.size()-1nums[i]nums[right1])right;}return rightleft?0:(right-left1);}
};时间复杂度O(n)空间复杂度O(1)
解法二简单排序
见官方题解排序之后与原数组不相同的左右指针位置即为中间数组的长度 C is_sorted()函数 此函数专门用于判断某个序列是否为有序序列。 和之前学习的其它排序函数比如 sorted() 函数一样is_sorted() 函数本质上就是一个函数模板定义在头文件中。因为在使用该函数之前程序中必须先引入此头文件。 is_sorted() 函数有 2 种语法格式分别是 //判断 [first, last) 区域内的数据是否符合 std::lessT 排序规则即是否为升序序列
bool is_sorted (ForwardIterator first, ForwardIterator last);
//判断 [first, last) 区域内的数据是否符合 comp 排序规则
bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);代码
class Solution {
public:int findUnsortedSubarray(vectorint nums) {if(is_sorted(nums.begin(),nums.end())){return 0;}vectorintnumsSorted(nums);sort(numsSorted.begin(),numsSorted.end());int left0;while(nums[left]numsSorted[left])left;int rightnums.size()-1;while(nums[right]numsSorted[right]){right--;}return right-left1; }
};时间复杂度O(nlogn)其中 n 为给定数组的长度。我们需要 O(nlogn) 的时间进行排序以及 O(n)的时间遍历数组因此总时间复杂度为 O(n)。
空间复杂度O(n其中 n 为给定数组的长度。我们需要额外的一个数组保存排序后的数组numsSorted。
29. 152 乘积最大子数组 解法动态规划
思路和算法
如果我们用 fmax(i)来表示以第 i个元素结尾的乘积最大子数组的乘积a 表示输入参数 nums那么根据「53. 最大子序和」的经验我们很容易推导出这样的状态转移方程 f max ( i ) max i 1 n { f ( i − 1 ) × a i , a i } f_{\max}(i) \max_{i 1}^{n} \{ f(i - 1) \times a_i, a_i \} fmax(i)maxi1n{f(i−1)×ai,ai}
它表示以第 i个元素结尾的乘积最大子数组的乘积可以考虑 a i a_i ai加入前面的 f max ( i − 1 ) f_{\max}(i - 1) fmax(i−1)对应的一段或者单独成为一段这里两种情况下取最大值。求出所有的 f max ( i ) f_{\max}(i) fmax(i) 之后选取最大的一个作为答案。
可是在这里这样做是错误的。为什么呢
因为这里的定义并不满足「最优子结构」。具体地讲如果 a { 5 , 6 , − 3 , 4 , − 3 } a \{ 5, 6, -3, 4, -3 \} a{5,6,−3,4,−3}那么此时 f max f_{\max} fmax对应的序列是 { 5 , 30 , − 3 , 4 , − 3 } \{ 5, 30, -3, 4, -3 \} {5,30,−3,4,−3}按照前面的算法我们可以得到答案为 30即前两个数的乘积而实际上答案应该是全体数字的乘积。我们来想一想问题出在哪里呢问题出在最后一个 −3 所对应 f max f_{\max} fmax的值既不是 −3也不是 4×(−3)而是 5×6×(−3)×4×(−3)。所以我们得到了一个结论当前位置的最优解未必是由前一个位置的最优解转移得到的。
我们可以根据正负性进行分类讨论。
考虑当前位置如果是一个负数的话那么我们希望以它前一个位置结尾的某个段的积也是个负数这样就可以负负得正并且我们希望这个积尽可能「负得更多」即尽可能小。如果当前位置是一个正数的话我们更希望以它前一个位置结尾的某个段的积也是个正数并且希望它尽可能地大。于是这里我们可以再维护一个 f min ( i ) f_{\min}(i) fmin(i)它表示以第 i 个元素结尾的乘积最小子数组的乘积那么我们可以得到这样的动态规划转移方程 f max ( i ) max i 1 n { f max ( i − 1 ) × a i , f min ( i − 1 ) × a i , a i } f min ( i ) min i 1 n { f max ( i − 1 ) × a i , f min ( i − 1 ) × a i , a i } \begin{aligned} f_{\max}(i) \max_{i 1}^{n} \{ f_{\max}(i - 1) \times a_i, f_{\min}(i - 1) \times a_i, a_i \} \\ f_{\min}(i) \min_{i 1}^{n} \{ f_{\max}(i - 1) \times a_i, f_{\min}(i - 1) \times a_i, a_i \} \end{aligned} fmax(i)fmin(i)i1maxn{fmax(i−1)×ai,fmin(i−1)×ai,ai}i1minn{fmax(i−1)×ai,fmin(i−1)×ai,ai}
它代表第 i 个元素结尾的乘积最大子数组的乘积 f max ( i ) f_{\max}(i) fmax(i)可以考虑把 a i a_i ai 加入第 i−1 个元素结尾的乘积最大或最小的子数组的乘积中二者加上 a i a_i ai三者取大就是第 i个元素结尾的乘积最大子数组的乘积。第 i个元素结尾的乘积最小子数组的乘积 f min ( i ) f_{\min}(i) fmin(i) max_element()和 min_element函数简介 max_element与min_element分别用来求最大元素和最小元素的位置。 接收参数容器的首尾地址迭代器可以是一个区间返回最值元素的地址迭代器需要减去序列头以转换为下标 代码
class Solution {
public:int maxProduct(vectorint nums) {vectorintmaxF(nums),minF(nums);int maxNumnums[0];for(int i1;inums.size();i){maxF[i]max(maxF[i-1]*nums[i],max(nums[i],minF[i-1]*nums[i]));if(maxF[i]maxNum)maxNummaxF[i];minF[i]min(minF[i-1]*nums[i],min(nums[i],maxF[i-1]*nums[i]));}return maxNum;}
};时间复杂度O(n)
空间复杂度O(n)
优化方法由于第 i个状态只和第 i−1个状态相关根据「滚动数组」思想我们可以只用两个变量来维护 、i−1 时刻的状态一个维护 f max f_{\max} fmax 一个维护 f min f_{\min} fmin
class Solution {
public:int maxProduct(vectorint nums) {int maxFnums[0],minFnums[0],ansnums[0];for(int i1;inums.size();i){int mxmaxF;int mn minF;maxFmax(mx*nums[i],max(nums[i],mn*nums[i]));minF min(mn * nums[i], min(nums[i], mx * nums[i]));ans max(maxF, ans);}return ans;}
};30. 334 递增的三元子序列 解法一贪心
可以使用贪心的方法将空间复杂度降到 O(1)。从左到右遍历数组 nums遍历过程中维护两个变量first 和 second分别表示递增的三元子序列中的第一个数和第二个数任何时候都有 firstsecond。
初始时firstnums[0]second∞。对于 1≤in当遍历到下标 i 时令 numnums[i]进行如下操作
如果 numsecond则找到了一个递增的三元子序列返回 true
否则如果 numfirst则将 second 的值更新为 num
否则将 first 的值更新为 num。
如果遍历结束时没有找到递增的三元子序列返回 false。
上述做法的贪心思想是为了找到递增的三元子序列first 和second 应该尽可能地小此时找到递增的三元子序列的可能性更大。
代码
class Solution {
public:bool increasingTriplet(vectorint nums) {int nnums.size();if(n3)return false;int firstnums[0],secondINT_MAX;for(int i1;in;i){int numnums[i];if(numsecond)return true;else if(numfirst){secondnum;}else{firstnum;}}return false; }
};时间复杂度O(n)其中 n 是数组 nums 的长度。需要遍历数组一次。
空间复杂度O(1)
解法二双向遍历
见官方题解334. 递增的三元子序列 - 力扣LeetCode
代码
class Solution {
public:bool increasingTriplet(vectorint nums) {int nnums.size();if(n3)return false;vectorintleftMin(n),rightMax(n);leftMin[0]nums[0];rightMax[n-1]nums[n-1];for(int i1;in;i){leftMin[i]min(leftMin[i-1],nums[i]);} for(int in-2;i0;i--){rightMax[i]max(rightMax[i1],nums[i]);}for(int i1;in-1;i){if(nums[i]leftMin[i-1]nums[i]rightMax[i1])return true;}return false;}
};时间复杂度O(n)其中 n是数组 nums 的长度。需要遍历数组三次。
空间复杂度O(n)其中 n 是数组 nums 的长度。需要创建两个长度为 n 的数组 leftMin 和 rightMax。
31. 376 摆动序列 解法一动态规划
本题大家都很容易想到用动态规划来求解求解的过程类似最长上升子序列不过是需要判断两个序列。大家在实现动态规划的平方复杂度时就会考虑如何优化到线性复杂度。
假设 up[i] 表示 nums[0:i] 中最后两个数字递增的最长摆动序列长度down[i] 表示 nums[0:i] 中最后两个数字递减的最长摆动序列长度只有一个数字时默认为 1。
接下来我们进行分类讨论 nums[i1] nums[i] 假设 down[i] 表示的最长摆动序列的最远末尾元素下标正好为 i遇到新的上升元素后up[i1] down[i] 1 这是因为 up 一定从 down 中产生初始除外并且 down[i] 此时最大。 假设 down[i] 表示的最长摆动序列的最远末尾元素下标小于 i设为 j那么 nums[j:i] 一定是递增的因为若完全递减最远元素下标等于 i若波动那么 down[i] down[j]。由于 nums[j:i] 递增down[j:i] 一直等于 down[j] 依然满足 up[i1] down[i] 1 。 nums[i1] nums[i]类似第一种情况 nums[i1] nums[i]新的元素不能用于任何序列保持不变 并且注意到 down 和 up 只和前一个状态有关所以我们可以优化存储分别用一个变量即可。 代码
class Solution {
public:int wiggleMaxLength(vectorint nums) {int up1,down1;if(nums.size()0)return 0;for(int i1;inums.size();i){if(nums[i]nums[i-1])updown1;else if(nums[i]nums[i-1]){downup1;} }return max(up,down); }
};时间复杂度O(n)其中 n 是序列的长度。我们只需要遍历该序列一次。
空间复杂度O(1)。我们只需要常数空间来存放若干变量。
解法二贪心
见题解376. 摆动序列 - 力扣LeetCode
代码
class Solution {
public:int wiggleMaxLength(vectorint nums) {if(nums.size()1)return 1;if(nums.size()2)return nums[0]nums[1]?1:2;//2. up变量记录趋势往上还是往下int index1;while(indexnums.size()nums[index]nums[index-1]){index;}if(indexnums.size())return 1;bool upnums[index]nums[index-1];//此时maxlen的长度至少为2int maxlen2,diff;for(int iindex1;inums.size();i){diffnums[i]-nums[i-1];if((diff0!up)||(diff0up)){maxlen;up!up;}}return maxlen; }
};32. 659 分割数组为连续子序列 解法一贪心 首先使用两个哈希表nc和tail
nc[i]存储原数组中数字i出现的次数 tail[i]存储以数字i结尾的且符合题意的连续子序列个数 先去寻找一个长度为3的连续子序列 i, i1, i2找到后就将 nc[i], nc[i1], nc[i2] 中对应数字消耗1个即-1并将 tail[i2] 加 1即以 i2 结尾的子序列个数 1。 如果后续发现有能够接在这个连续子序列的数字 i3则延长以 i2 为结尾的连续子序列到 i3此时消耗 nc[i3] 一个由于子序列已延长因此tail[i2] 减 1tail[i3] 加 1 在不满足上面的情况下 如果 nc[i] 为 0说明这个数字已经消耗完可以不管了 如果 nc[i] 不为 0说明这个数字多出来了且无法组成连续子序列所以可以直接返回 false 了 因此只有检查到某个数时这个数未被消耗完且既不能和前面组成连续子序列也不能和后面组成连续子序列时无法分割
代码
class Solution {
public:bool isPossible(vectorint nums) {int nnums.size();if(n3)return false;unordered_mapint,intnc,tail;for(auto num:nums){nc[num];}for(auto num:nums){if(nc[num]0)continue;else if(nc[num]0tail[num-1]0){tail[num-1]--;tail[num];nc[num]--;}else if(nc[num]0nc[num1]0nc[num2]0){nc[num]--;nc[num1]--;nc[num2]--;tail[num2];}else{return false;}}return true;}
};时间复杂度O(N)所有元素遍历一遍 O(N)循环内部均为常数时间操作 O(1) 空间复杂度O(N)使用了两个哈希 map
解法二哈希表 最小堆
见官方题解659. 分割数组为连续子序列 - 力扣LeetCode
33. 343 整数拆分 解法一动态规划
对于正整数 n当 n≥2 时可以拆分成至少两个正整数的和。令 x 是拆分出的第一个正整数则剩下的部分是 n−xn−x可以不继续拆分或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积因此可以使用动态规划求解。
创建数组 dp其中 dp[i] 表示将正整数 i拆分成至少两个正整数的和之后这些正整数的最大乘积。特别地0 不是正整数1 是最小的正整数0 和 1 都不能拆分因此 dp[1]1;
当 i≥2 时假设对正整数 i拆分出的第一个正整数是 j1≤ji则有以下两种方案
将 i 拆分成 j和 i−j 的和且 i−j不再拆分成多个正整数此时的乘积是 j×(i−j)
将 i 拆分成 j 和 i−j 的和且 i−j 继续拆分成多个正整数此时的乘积是 j×dp[i−j]。
因此当 j 固定时有 dp [ i ] max ( j × ( i − j ) , j × dp [ i − j ] ) \textit{dp}[i]\max(j \times (i-j), j \times \textit{dp}[i-j]) dp[i]max(j×(i−j),j×dp[i−j])。由于 j 的取值范围是 1 到 i−1需要遍历所有的 j 得到 dp[i] 的最大值因此可以得到状态转移方程如下 dp [ i ] max 1 ≤ j i { max ( j × ( i − j ) , j × dp [ i − j ] ) } \textit{dp}[i]\mathop{\max}\limits_{1 \le j i}\{\max(j \times (i-j), j \times \textit{dp}[i-j])\} dp[i]1≤jimax{max(j×(i−j),j×dp[i−j])}
最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后这些正整数的最大乘积。
优化版的动态规划见343. 整数拆分 - 力扣LeetCode
解法二数学推导
见https://leetcode.cn/problems/integer-break/solutions/
拆分规则 最优 3 。把数字 n 可能拆为多个因子 3 余数可能为 0,1,2 三种情况。 次优 2 。若余数为 2 则保留不再拆为 11 。 最差 1。若余数为 1 则应把一份 31 替换为 22因为 2×23×1
34. 496 下一个更大元素I 解法一双重循环
最简单的方法就是对于nums1中的所有元素遍历nums2找到其所在的位置并且寻找该位置后是否有比其大的数若有则将此数字加入res数组否则将-1加入res数组
代码
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {vectorintres;for(int ns1:nums1){for(int i0;inums2.size();i){if(nums2[i]ns1){int ji;int greaterNs1-1;while(jnums2.size()){if(nums2[j]ns1){greaterNs1nums2[j];break;}j;}res.push_back(greaterNs1);break;}}}return res;}
};时间复杂度O(mn)其中 m 是 nums1的长度n是 nums2 的长度。
空间复杂度O(1)。
解法二 单调栈hash表
思路
我们可以先预处理 nums2 使查询 nums1中的每个元素在 nums2中对应位置的右边的第一个更大的元素值时不需要再遍历 nums2。于是我们将题目分解为两个子问题
第 1个子问题如何更高效地计算 nums2 中每个元素右边的第一个更大的值
第 2 个子问题如何存储第 1 个子问题的结果。
算法
我们可以使用单调栈来解决第 1 个子问题。倒序遍历 nums2并用单调栈中维护当前位置右边的更大的元素列表从栈底到栈顶的元素是单调递减的。
具体地每次我们移动到数组中一个新的位置 i就将当前单调栈中所有小于 nums2的元素弹出单调栈当前位置右边的第一个更大的元素即为栈顶元素如果栈为空则说明当前位置右边没有更大的元素。随后我们将位置 i的元素入栈。
细节
因为在这道题中我们只需要用到 nums2 中元素的顺序而不需要用到下标所以栈中直接存储 nums2中元素的值即可。
代码
class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {unordered_mapint,int numToGreater;stackintst;for(int inums2.size()-1;i0;i--){int nnums2[i];while(!st.empty()st.top()n){st.pop();}if(st.empty())numToGreater[n]-1;elsenumToGreater[n]st.top();st.push(n);}vectorintres(nums1.size());for(int i0;inums1.size();i){res[i]numToGreater[nums1[i]];}return res;}
};时间复杂度O(mn)其中 m 是 nums1的长度n 是 nums2 的长度。我们需要遍历 nums2以计算 nums2中每个元素右边的第一个更大的值需要遍历 nums1 以生成查询结果。
空间复杂度O(n)用于存储哈希表。
35. 503 下一个更大的元素|| 解法一简单模拟
即我们利用取模来作为循环数组的循环对于nums中的每一个元素若是从这个元素后一个元素循环回到当前元素都未找到比它大的数则将-1加入解否则将得到的比当前元素大的值加入解。
代码
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {vectorintres(nums.size(),-1);int nnums.size();for(int i0;in;i){int cnt1;int j(i1)%n;while(cntn){if(nums[j]nums[i]){res[i]nums[j];break;}j(j1)%n;cnt;}}return res;}
};时间复杂度O(n^2)
空间复杂度O(1)
解法二利用496做法中的单调栈循环数组
本题如果暴力求解对于每个元素都向后去寻找比它更大的元素那么时间复杂度 O(N2)O(N^2)O(N 2 ) 会超时。必须想办法优化。
我们注意到暴力解法中如果数组的前半部分是单调不增的那么会有很大的计算资源的浪费。比如说 [6,5,4,3,8]对于前面的 [6,5,4,3] 等数字都需要向后遍历当寻找到元素 8 时才找到了比自己大的元素而如果已知元素 6 向后找到元素 8 才找到了比自己的大的数字那么对于元素 [5,4,3] 来说它们都比元素 6 更小所以比它们更大的元素一定是元素 8不需要单独遍历对 [5,4,3] 向后遍历一次
根据上面的分析可知可以遍历一次数组如果元素是单调递减的则他们的「下一个更大元素」相同我们就把这些元素保存直到找到一个较大的元素把该较大元素逐一跟保存了的元素比较如果该元素更大那么它就是前面元素的「下一个更大元素」。
在实现上我们可以使用「单调栈」来实现单调栈是说栈里面的元素从栈底到栈顶是单调递增或者单调递减的类似于汉诺塔。
本题应该用个「单调递减栈」来实现。
建立「单调递减栈」并对原数组遍历一次
如果栈为空则把当前元素放入栈内 如果栈不为空则需要判断当前元素和栈顶元素的大小 如果当前元素比栈顶元素大说明当前元素是前面一些元素的「下一个更大元素」则逐个弹出栈顶元素直到当前元素比栈顶元素小为止。 如果当前元素比栈顶元素小说明当前元素的「下一个更大元素」与栈顶元素相同则把当前元素入栈。 注意由于我们要找每一个元素的下一个更大的值因此我们需要对原数组遍历两次对遍历下标进行取余转换。 以及因为栈内存放的是还没更新答案的下标可能会有位置会一直留在栈内最大值的位置因此我们要在处理前预设答案为 -1。而从实现那些没有下一个更大元素不出栈的位置的答案是 -1。 代码
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {vectorintres(nums.size(),-1);stackintst;int nnums.size();for(int i0;i2*n;i){while(!st.empty()nums[st.top()]nums[i%n]){res[st.top()]nums[i%n];st.pop();}st.push(i%n);}return res;}
};时间复杂度: O(n)其中 n 是序列的长度。我们需要遍历该数组中每个元素最多 2 次每个元素出栈与入栈的总次数也不超过 4 次。
空间复杂度: O(n其中 n 是序列的长度。空间复杂度主要取决于栈的大小栈的大小至多为 2n−1。
36. 456 132模式 解法一贪心暴力求解【超时】
这个方法就是 O(N2)的解法是这个题的暴力解法。
我选择的方法是维护 132模式 中间的那个数字 3因为 3 在 132 的中间的数字、也是最大的数字。我们的思路是个贪心的方法我们要维护的 1 是 3 左边的最小的数字 2 是 3 右边的比 3 小并且比 1 大的数字。
从左到右遍历一次遍历的数字是 nums[j] 也就是 132 模式中的 3。根据上面的贪心思想分析我们想让 1 是 3 左边最小的元素然后使用暴力nums[j1…N−1] 中找到 132 模式中的 2 就行。 这种做法会超时 解法二单调栈
我们从后往前做维护一个「单调递减」的栈同时使用 knum 记录所有出栈元素的最大值次大值。
那么当我们遍历到 i只要满足发现满足 nums[i] knum 说明我们找到了符合条件的 i j k。
举例子对于样例数据 [3, 1, 4, 2]我们知道满足 132 结构的子序列是 [1, 4, 2]其处理逻辑是遍历从后往前
枚举到 2栈内元素为 [2]k INF 枚举到 4不满足「单调递减」2 出栈更新 knum 4 入栈。栈内元素为 [4] knum 2 枚举到 1满足 nums[i] knum 说明对于 i 而言后面有一个比其大的元素满足 num[i] knum 的条件同时这个 knum 的来源又是因为维护「单调递减」而弹出导致被更新的满足 knum有比 k 要大的元素并且knum的索引位置大于此元素的索引位置。因此我们找到了满足 132 结构的组合。 这样做的本质是我们通过维护「单调递减」来确保已经找到了有效的 (jnum,knum)。换句话说如果 knum有值的话那么必然是因为有 jnum knum导致的有值。也就是 132 结构中我们找到了 32剩下的 i 也就是 132 结构中的 1则是通过遍历过程中与 knum的比较来找到。这样做的复杂度是 O(n 的比树状数组还要快。 代码
class Solution {
public:bool find132pattern(vectorint nums) {stackintst;int nnums.size();int knumINT_MIN;for(int in-1;i0;i--){if(nums[i]knum){return true;}while(!st.empty()st.top()nums[i]){knummax(knum,st.top());st.pop();}st.push(nums[i]);}return false;}};时间复杂度O(n)空间复杂度O(n)
37. 316 去除重复字母 解法贪心单调栈
注意题目要求1.要去重2.不能打乱字符的相对顺序 3.需要返回去重后字典序最小的结果
贪心的做法就是保证每一步的字符都是最小的其可以使用【单调栈】来解决只不过需要添加额外的数据结构用于记录字符的个数以及是否在栈中
遍历一遍字符串使用wordNum记录每个字符的出现个数利用isInstack初始化所有的字符都不在栈中为0此时我们从左到右遍历字符串每遍历一个字符c该字符出现的次数减一即wordNum[c]-1; 判断如果c已经在栈中则跳过否则就判断c和当前栈顶的字符t谁大假如c比t小并且t此时的出现次数0,那么将栈顶元素弹出将c作为栈顶元素能让字典序降低所以我们对于栈中比c小并且出现次数大于0的字符全都弹出并设置标识为isInstack为false;最后将c加入栈中并设置标识为isInstack为true;最后我们返回的结果的逆序就是最终结果
代码
class Solution {
public:string removeDuplicateLetters(string s) {unordered_mapint,intwordNum;vectorintisInstack(256,0);for(auto c:s){wordNum[c];}stackcharst;for(int i0;is.size();i){char cs[i];wordNum[c]--;if(isInstack[c]){continue;}while(!st.empty()cst.top()){if(wordNum[st.top()]0){isInstack[st.top()]0;st.pop();}else{break;}}st.push(c);isInstack[st.top()]1;}string res;while(!st.empty()){resst.top();st.pop();}reverse(res.begin(),res.end());return res;}
};时间复杂度O(N)其中 N 为字符串长度。代码中虽然有双重循环但是每个字符至多只会入栈、出栈各一次。
空间复杂度 O ( ∣ Σ ∣ ) O(|\Sigma|) O(∣Σ∣)其中 Σ为字符集合本题中字符均为小写字母所以 ∣Σ∣26|。由于栈中的字符不能重复因此栈中最多只能有 ∣Σ∣|个字符另外需要维护两个数组分别记录每个字符是否出现在栈中以及每个字符的剩余数量。
38. 402 移掉k位数字 解法单调栈贪心
对于两个相同长度的数字序列最左边不同的数字决定了这两个数字的大小例如对于 A1axxxB1bxxx如果 ab 则 AB。
基于此我们可以知道若要使得剩下的数字最小需要保证靠前的数字尽可能小。
让我们从一个简单的例子开始。给定一个数字序列例如 425如果要求我们只删除一个数字那么从左到右我们有 4、2和 5 三个选择。我们将每一个数字和它的左邻居进行比较。从 2 开始2 小于它的左邻居 4。假设我们保留数字 4那么所有可能的组合都是以数字 4即 42、4开头的。相反如果移掉 4留下 2我们得到的是以 2 开头的组合即 25这明显小于任何留下数字 4的组合。因此我们应该移掉数字 4。如果不移掉数字 4则之后无论移掉什么数字都不会得到最小数。
基于上述分析我们可以得出「删除一个数字」的贪心策略给定一个长度为 n的数字序列 [ D 0 D 1 D 2 D 3 … D n − 1 ] [D_0D_1D_2D_3\ldots D_{n-1}] [D0D1D2D3…Dn−1]从左往右找到第一个位置 ii0使得 D i D i − 1 D_iD_{i-1} DiDi−1并删去 D i − 1 D_{i-1} Di−1如果不存在说明整个数字序列单调不降删去最后一个数字即可。
思路
考虑从左往右增量的构造最后的答案。我们可以用一个栈维护当前的答案序列栈中的元素代表截止到当前位置删除不超过 k 次个数字后所能得到的最小整数。根据之前的讨论在使用 k 个删除次数之前栈中的序列从栈底到栈顶单调不降。
因此对于每个数字如果该数字小于栈顶元素我们就不断地弹出栈顶元素直到
栈为空或者新的栈顶元素不大于当前数字或者我们已经删除了 k 位数字
代码实现中注意的细节 如果我们删除了 cnt 个数字且 cntk这种情况下我们需要从序列尾部删除额外的 k−m 个数字,可以简单的将最后得到的stk截取前n-k个即可。 如果最终的数字序列存在前导零我们要删去前导零。 如果最终数字序列为空我们应该返回 0 代码
class Solution {
public:string removeKdigits(string num, int k) {int nnum.size();if(nk){return 0;}string stk;int cnt0;for(int i0;in;i){char cnum[i];if(cntk){ stk.push_back(c);continue; } while(!stk.empty()stk.back()c){stk.pop_back();cnt;if(cntk)break;}stk.push_back(c);}stkstk.size()n-k?stk:stk.substr(0,n-k); string ans;bool isFirstDigitfalse;for(char c:stk){if(c!0){isFirstDigittrue;}if(isFirstDigit)ansc;}return ans?0:ans;}
};时间复杂度O(n)其中 n 为字符串的长度。尽管存在嵌套循环但内部循环最多运行 k 次。由于0k≤n主循环的时间复杂度被限制在 2n2n 以内。对于主循环之外的逻辑它们的时间复杂度是 O(n)因此总时间复杂度为O(n)。
空间复杂度O(n)。栈存储数字需要线性的空间。
39. 321 拼接最大数 解法单调栈分治
和402移掉k位数字类似只不不过这一次是两个数组而不是一个并且是求最大数。
最大最小是无关紧要的关键在于是两个数组并且要求从两个数组选取的元素个数加起来一共是 k。
然而在一个数组中取 k 个数字并保持其最小或者最大我们已经会了。但是如果问题扩展到两个会有什么变化呢
实际上问题本质并没有发生变化。 假设我们从 nums1 中取了 k1 个从 num2 中取了 k2 个其中 k1 k2 k。而 k1 和 k2 这 两个子问题我们是会解决的。由于这两个子问题是相互独立的因此我们只需要分别求解然后将结果合并即可。
假如 k1 和 k2 个数字已经取出来了。那么剩下要做的就是将这个长度分别为 k1 和 k2 的数字合并成一个长度为 k 的数组合并成一个最大的数组。
以题目的 nums1 [3, 4, 6, 5] nums2 [9, 1, 2, 5, 8, 3] k 5 为例。 假如我们从 num1 中取出 1 个数字那么就要从 nums2 中取出 4 个数字。
运用第一题的方法我们计算出应该取 nums1 的 [6]并取 nums2 的 [9,5,8,3]。 如何将 [6] 和 [9,5,8,3]使得数字尽可能大并且保持相对位置不变呢
实际上这个过程有点类似归并排序中的治而上面我们分别计算 num1 和 num2 的最大数的过程类似归并排序中的分。 我们将从 num1 中挑选的 k1 个数组成的数组称之为 A将从 num2 中挑选的 k2 个数组成的数组称之为 B。这里需要说明一下。 在很多编程语言中如果 A 和 B 是两个数组当前仅当 A 的首个元素字典序大于 B 的首个元素A B 返回 true否则返回 false。
具体算法
从 nums1 中 取 min(i,len(nums1)) 个数形成新的数组 A取的逻辑同第一题其中 i 等于 0,1,2, … k。 从 nums2 中 对应取 min(j,len(nums2)) 个数形成新的数组 B取的逻辑同第一题其中 j 等于 k - i。 注意我这里取数的上限即不能超过数组本身的长度这点容易大家忽略
将 A 和 B 按照上面的 merge 方法合并 上面我们暴力了 k 种组合情况我们只需要将 k 种情况取出最大值即可。 代码细节需要注意的是两个数组合并的过程中使用双指针itrA和itrB如果碰到数字相同的时候需要比较后续的数字直到数字不同才能决定加入A中的数字还是B中的数字。 C中编写了自定义compare函数进行比较主要就是从A的itrA和B的itrB开始利用A[itrA]-B[itrB]来比较两个的大小A和B都是vector,A[itrA]-B[itrB]计算的就是字典序的差值如果相同则循环比较后面的字符 代码
class Solution {
public:vectorintpick_max(vectorintnums,int k){vectorintres;int cntnums.size()-k;for(int i0;inums.size();i){while(cnt!res.empty()res.back()nums[i]){res.pop_back();cnt--;}res.push_back(nums[i]);}res.resize(k);return res;}int compare(vectorint A, int itrA, vectorint B, int itrB) {int x A.size(), y B.size();while (itrA x itrB y) {int difference A[itrA] - B[itrB];if (difference ! 0) {return difference;}itrA;itrB;}return (x - itrA) - (y - itrB);}vectorint merge(vectorintA,vectorintB){int lenA.size()B.size();vectorintans(len);int itrA0,itrB0;for(int i0;ilen;i){if(compare(A,itrA,B,itrB)0){ans[i]A[itrA];}else{ans[i]B[itrB];}}return ans;}vectorint maxNumber(vectorint nums1, vectorint nums2, int k) {vectorintres(k,0);for(int i0;ik;i){if(inums1.size()(k-i)nums2.size()){vectorintsub1pick_max(nums1,i);vectorintsub2pick_max(nums2,k-i);vectorintcur_resmerge(sub1,sub2);if(cur_resres)res.swap(cur_res);}}return res;}
};时间复杂度pick_max 的时间复杂度为 O(MN)其中 M 为 nums1 的长度N 为 nums2 的长度。 merge 的时间复杂度为 O(k)再加上外层遍历所有的 k 中可能性。因此总的时间复杂度为 O(k2∗(MN)。 空间复杂度我们使用了额外的 stack 和 ans 数组因此空间复杂度为 O(max(M,N,k))其中 M 为 nums1 的长度N 为 nums2 的长度。
40. 84 柱状图中最大的矩形 解法一单调栈哨兵【减少边界判断】
单调栈分为单调递增栈和单调递减栈
1.单调递增栈即栈内元素保持单调递增的栈
同理单调递减栈即栈内元素保持单调递减的栈 操作规则下面都以单调递增栈为例
2如果新的元素比栈顶元素大就入栈
如果新的元素较小那就一直把栈内元素弹出来直到栈顶比新元素小 加入这样一个规则之后会有什么效果
3.栈内的元素是递增的
当元素出栈时说明这个新元素是出栈元素向后找第一个比其小的元素 举个例子配合下图现在索引在 6 栈里是 1 5 6 。 接下来新元素是 2 那么 6 需要出栈。 当 6 出栈时右边 2 代表是 6 右边第一个比 6 小的元素。
当元素出栈后说明新栈顶元素是出栈元素向前找第一个比其小的元素 当 6 出栈时5 成为新的栈顶那么 5 就是 6 左边第一个比 6 小的元素。
那么就确定了6为矩形高度的最大面积即夹在5和2索引之间的宽度即left11【5的索引1】right3-1【右边的索引减1】
宽度wright-left12-21,面积为6*16
因此思路为
对于一个高度如果能得到向左和向右的边界那么就能对每个高度求一次面积遍历所有高度即可得出最大面积使用单调栈在出栈操作时得到前后边界并计算面积 注意增加了哨兵机制 弹栈的时候栈为空 遍历完成以后栈中还有元素 为此可以我们可以在输入数组的两端加上两个高度为 0 或者是 0.5只要比 1 严格小都行的柱形可以回避上面这两种分类讨论。 这两个站在两边的柱形有一个很形象的名词叫做哨兵Sentinel。 有了这两个柱形 左边的柱形第 1 个柱形由于它一定比输入数组里任何一个元素小它肯定不会出栈因此栈一定不会为空 右边的柱形第 2 个柱形也正是因为它一定比输入数组里任何一个元素小它会让所有输入数组里的元素出栈第 1 个哨兵元素除外。 这里栈对应到高度呈单调增加不减的形态因此称为单调栈Monotone Stack。它是暴力解法的优化计算每个柱形的高度对应的最大矩形的顺序由出栈顺序决定。 代码
class Solution {
public:int largestRectangleArea(vectorint heights) {int ans0;vectorintst;heights.insert(heights.begin(),0);heights.push_back(0);for(int i0;iheights.size();i){while(!st.empty()heights[st.back()]heights[i]){int curst.back();st.pop_back();int leftst.back()1;int righti-1;ansmax(ans,(right-left1)*heights[cur]);}st.push_back(i);}return ans;}
};时间复杂度O(N)。空间复杂度O(N)。
41. 85 最大矩形 解法
前缀和 单调栈 为了方便我们令 matrix 为 mat记矩阵的行高为 n矩阵的列宽为 m。
定义坐标系 : 左上角坐标为 (1,1)右下角坐标为 (n,m)。
我们将 mat 的每一行作为基准以基准线为起点往上连续 1 的个数为高度。
以题目样例进行说明 红框部分代表「以第一行作为基准线统计每一列中基准线及以上连续 111 的个数」此时只有第一行可得[1,0,1,0,0] 黄框部分代表「以第二行作为基准线统计每一列中基准线及以上连续 111 的个数」此时有第一行和第二行可得[2,0,2,1,1] 蓝框部分代表「以第三行作为基准线统计每一列中基准线及以上连续 111 的个数」此时有三行可得[3,1,3,2,2] … 将原矩阵进行这样的转换好处是 : 对于原矩中面积最大的矩形其下边缘必然对应了某一条基准线从而将问题转换为题解84. 柱状图中最大的矩形 。
预处理基准线数据可以通过前缀和思想来做构建一个二维数组 sum为了方便我们令二维数组下标从 1 开始并从上往下地构造 s u m [ i ] [ j ] { 0 m a t [ i ] [ j ] 0 s u m [ i − 1 ] [ j ] 1 m a t [ i ] [ j ] 1 sum[i][j] \begin{cases} 0 mat[i][j] 0 \\ sum[i - 1][j] 1 mat[i][j] 1 \\ \end{cases} sum[i][j]{0sum[i−1][j]1mat[i][j]0mat[i][j]1
当有了 sum 之后则是和 题解84. 柱状图中最大的矩形 一样的做法 : 枚举高度 单调栈,直接调用84题函数。
代码
class Solution {
public:int maximalRectangle(vectorvectorchar matrix) {int nmatrix.size(),mmatrix[0].size(),ans0;vectorvectorintsum(n10,vectorint(m10,0));for(int i1;in;i){for(int j1;jm;j){sum[i][j]matrix[i-1][j-1]0?0:sum[i-1][j]1;}}for(int i1;in;i){vectorintheightssum[i];ansmax(ans,largestRectangleArea(heights));}return ans;}int largestRectangleArea(vectorint heights) {int ans0;vectorintst;heights.insert(heights.begin(),0);heights.push_back(0);for(int i0;iheights.size();i){while(!st.empty()heights[st.back()]heights[i]){int curst.back();st.pop_back();int leftst.back()1;int righti-1;ansmax(ans,(right-left1)*heights[cur]);}st.push_back(i);}return ans;}
};时间复杂度O(n×m空间复杂度O(n×m)
