今天写了四道题！尽管前两道很简单（所以没放到标题里面）。难度范围：★~★★★，昨天最后一道困难题是打击到我了，但没关系，我自己会从简单题中找安慰（倒）。
今天的主要收获：学到了单调栈的使用；认识了tolower函数和emplace_back函数
其实收获不止这些，但我就是不知道怎么写出来，下次一定写得面面俱到
一.最大连续1的数 ★☆☆☆☆
题目
485. 最大连续 1 的个数 给定一个二进制数组nums， 计算其中最大连续1的个数。
思路
遍历数组，用count记录当前连续的1的个数，res记录count的最大值，当遍历到的数字为1时，count++，反之使count=0。
代码
class Solution { public: int findMaxConsecutiveOnes(vector<int>& nums) { int len=nums.size(); int res=0; int count=0; for(int i=0;i<len;i++){ count = nums[i]==1 ? count+1 : 0; res = count > res ? count : res; } return res; } };复杂度
n为数组的长度
时间复杂度：O(n)。循环n次
空间复杂度：O(1)
二.提莫攻击 ★☆☆☆☆
题目
495. 提莫攻击 在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
当提莫攻击艾希，艾希的中毒状态正好持续duration秒。
正式地讲，提莫在t发起攻击意味着艾希在时间区间[t, t + duration - 1]（含t和t + duration - 1）处于中毒状态。如果提莫在中毒影响结束前再次攻击，中毒状态计时器将会重置，在新的攻击之后，中毒影响将会在duration秒后结束。
给你一个非递减的整数数组timeSeries，其中timeSeries[i]表示提莫在timeSeries[i]秒时对艾希发起攻击，以及一个表示中毒持续时间的整数duration。
返回艾希处于中毒状态的总秒数。
思路
用pre记录前一次攻击的时间，cur记录这一次攻击的时间，如果两次攻击时间间隔>=duration，前一次攻击造成的中毒持续时间仍为duration；如果时间间隔<duration，前一次攻击造成的中毒持续状态为 两次攻击的时间间隔。
注意：最终的结果res要加上最后一次攻击造成的中毒持续时间duration
代码
class Solution { public: int findPoisonedDuration(vector<int>& timeSeries, int duration) { int len=timeSeries.size(); int res=0; for(int i=1;i<len;i++){ int pre=timeSeries[i-1]; int cur=timeSeries[i]; if(cur-pre >= duration){ res+=duration; }else{ res+=cur-pre; } } //加上最后一次攻击的中毒时间 res+=duration; return res; } };复杂度
n为数组长度
时间复杂度：O(n)
空间复杂度：O(1)
三.下一个更大的元素 ★★☆☆☆☆
题目
496. 下一个更大元素 Inums1中数字x的下一个更大元素是指x在nums2中对应位置右侧的第一个比x大的元素。
给你两个没有重复元素的数组nums1和nums2，下标从0开始计数，其中nums1是nums2的子集。
对于每个0 <= i < nums1.length，找出满足nums1[i] == nums2[j]的下标j，并且在nums2确定nums2[j]的下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是-1。
返回一个长度为nums1.length的数组ans作为答案，满足ans[i]是如上所述的下一个更大元素。
思路1
遍历数组nums1，对nums1的每一个元素num，都遍历数组nums2，找到与之相等的元素的位置，再对数组nums2的该位置之后的数组进行遍历，找第一个比num大的元素。
使用一个变量flag，记录是否找到更大的元素，如果找到了将其放入结果数组，并置flag为1；如果将对应位置之后的元素都遍历了flag仍为0，说明没找到，将-1加入ans中。
最后返回ans即可。
注意：找到之后利用break及时返回，避免找的更大的元素不是第一个，以及避免找到与nums1[1]相等的元素之后的无效遍历。
代码
class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { int len1=nums1.size(); int len2=nums2.size(); vector<int> ans; int index=0; //遍历两个数组 for(int i=0;i<len1;i++){ for(int j=0;j<len2;j++){ if(nums2[j]!=nums1[i]){ continue; } int flag=0;//标记是否找到更大的数 //找到和nums1[i]相等的nums2[j] //遍历j之后的数 for(int k=j+1;k<len2;k++){ //找第一个更大的数 if(nums2[k]>nums2[j]){ ans.push_back(nums2[k]); flag=1; break;//直接退出 } } //没找到记作-1 if(flag==0){ ans.push_back(-1); } break;//继续nums1的下一个元素nums1[i+1] } } return ans; } };复杂度
m、n分别是两个数组nums1、nums2的长度
时间复杂度：O(mn)。虽然看起来有三层循环，但是第三层和第二层循环次数加起来最大为n，所有总的时间复杂度为O(mn)
空间复杂度：O(1)。
思路2
使用哈希表记录数组nums2的元素和索引，查找num时可以之间找到对应索引。
看起来好像方便，但是不仅没有降低时间复杂度，还增加了空间复杂度（跪地）
代码
class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { int len1=nums1.size(); int len2=nums2.size(); vector<int> ans; unordered_map<int,int> map;//哈希表存储nums2的值 for(int i=0;i<len2;i++){ map[nums2[i]]=i; } for(int i=0;i<len1;i++){ int j=map[nums1[i]]+1;//找到nums2中数值为nums1[i]的数的下一个数的索引 int flag=0;//标记是否找到更大的元素 while(j<len2){ if(nums2[j]>nums1[i]){ //找到 ans.push_back(nums2[j]); flag=1; break;//退出循环 } j++; } if(flag==0){ //没找到 ans.push_back(-1); } } return ans; } };复杂度
m、n分别是两个数组nums1、nums2的长度
时间复杂度：O(m×n)
空间复杂度：O(n)。哈希表的空间。
官方题解——单调栈+哈希表 ★★★☆☆
可以将问题分为两个子问题：
1.如何高效地找到第一个更大的元素
2.如何保存第一个子问题的结果
解答：
1.利用单调栈：从后往前遍历数组nums2，重复操作：如果栈顶元素小于当前元素num，则将栈顶元素移除；并将当前元素num放入栈中。因为要找nums1的元素 num ，在nums2中的位置之后的第一个比它大的数字，记为x，那么在num和x之间的数肯定比 x 小；而在 x 之后的数即使比num大也不是第一个
2.利用哈希表：将元素值与其右边第一个更大的元素值的对应关系存入哈希表。
3.在遍历数组nums2的时候就可以将哈希表初始化了：如果遍历到元素num时，栈为空，说明右边没有更大的元素，将该位置的哈希表的元素值置为0；反之置为栈顶元素，因为栈定元素是最靠近当前元素num的。
相当于对nums2的所有元素都进行了找其右边第一个更大元素的操作，最后再对nums1的元素利用哈希表查找即可。
代码
class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { unordered_map<int,int> map; stack<int> st; for(int i=nums2.size()-1;i>=0;--i){ int num=nums2[i]; while(!st.empty() && num>=st.top()){ st.pop(); } map[num]=st.empty()?-1:st.top(); st.push(num); } vector<int> ans(nums1.size()); for(int i=0;i<nums1.size();++i){ ans[i]=map[nums1[i]]; } return res; } };复杂度
m、n分别是两个数组nums1、nums2的长度
时间复杂度：O(m+n) —— 遍历 nums2 以计算 nums2 中每个元素右边的第一个更大的值；需要遍历 nums1 以生成查询结果
空间复杂度：O(n) —— 用于存储哈希表
四.键盘行 ★★★☆☆
题目
500. 键盘行 给你一个字符串数组words，只返回可以使用在美式键盘同一行的字母打印出来的单词。键盘如下图所示。
请注意，字符串不区分大小写，相同字母的大小写形式都被视为在同一行。
思路
1.用三个字符串记录每一行的字母，通过c++的字符串.find()函数判断字符是否存在于字符串中
2.通过遍历字符串数组的每一个字符串，记录第一个字符所在的行对应的字符串 s，遍历剩余字符，如果不在同一行，直接退出，进行下一个字符串的判断。
代码1（有误）
class Solution { public: vector<string> findWords(vector<string>& words) { vector<string> res;//结果数组 string s1="qwertyuiopQWERTYUIOP"; string s2="asdfghjklASDFGHJKL"; string s3="zxcvbnmZXCVBNM"; for(int i=0;i<words.size();i++){ string str=words[i]; string s; if(s1.find(str[0])!= string::npos){ s=s1; }else if(s2.find(str[0])!= string::npos){ s=s2; }else{ s=s3; } for(int j=1;j<str.size();j++){ char ch=str[j]; //和第一个字符不是同一行 if(s.find(ch) == string::npos){ break; } //所有字符都是同一行，放入结果数组 if(j==str.size()-1){ res.push_back(str); } } } return res; } };上诉代码遇到由单个字母组成的字符串时，无法实现正确的处理，所以还需要增加对特殊情况的处理
代码2
class Solution { public: vector<string> findWords(vector<string>& words) { vector<string> res;//结果数组 string s1="qwertyuiopQWERTYUIOP"; string s2="asdfghjklASDFGHJKL"; string s3="zxcvbnmZXCVBNM"; for(int i=0;i<words.size();i++){ string str=words[i]; //当字符串长度为1时，直接将其加入res if(str.size()==1){ res.push_back(str); }else{ string s; if(s1.find(str[0])!= string::npos){ s=s1; }else if(s2.find(str[0])!= string::npos){ s=s2; }else{ s=s3; } for(int j=1;j<str.size();j++){ char ch=str[j]; //和第一个字符不是同一行 if(s.find(ch) == string::npos){ break; } //所有字符都是同一行，放入结果数组 if(j==str.size()-1){ res.push_back(str); } } } } return res; } };代码3
增加了flag标志变量，不满足条件时赋值为false，遍历完每个单词后若仍为true，将其加入res
class Solution { public: vector<string> findWords(vector<string>& words) { vector<string> res;//结果数组 string s1="qwertyuiopQWERTYUIOP"; string s2="asdfghjklASDFGHJKL"; string s3="zxcvbnmZXCVBNM"; for(int i=0;i<words.size();i++){ string str=words[i]; string s; if(s1.find(str[0])!= string::npos){ s=s1; }else if(s2.find(str[0])!= string::npos){ s=s2; }else{ s=s3; } bool flag=true; for(int j=1;j<str.size();j++){ char ch=str[j]; //和第一个字符不是同一行 if(s.find(ch) == string::npos){ flag=false; break; } } if(flag){ res.push_back(str); } } return res; } };复杂度
n为字符串数组的长度，即单词的个数；m为单词的平均长度
时间复杂度：O(nm)
空间复杂度：O(1)
代码4
来自于豆包看了我的代码后，给出的优化建议——创建哈希表存储
class Solution { public: vector<string> findWords(vector<string>& words) { vector<string> res;//结果数组 // 预先构建字符到行号的映射 unordered_map<char, int> char2row = { {'q',1},{'w',1},{'e',1},{'r',1},{'t',1},{'y',1},{'u',1},{'i',1},{'o',1},{'p',1}, {'Q',1},{'W',1},{'E',1},{'R',1},{'T',1},{'Y',1},{'U',1},{'I',1},{'O',1},{'P',1}, {'a',2},{'s',2},{'d',2},{'f',2},{'g',2},{'h',2},{'j',2},{'k',2},{'l',2}, {'A',2},{'S',2},{'D',2},{'F',2},{'G',2},{'H',2},{'J',2},{'K',2},{'L',2}, {'z',3},{'x',3},{'c',3},{'v',3},{'b',3},{'n',3},{'m',3}, {'Z',3},{'X',3},{'C',3},{'V',3},{'B',3},{'N',3},{'M',3} }; // 查找行号只需 O(1) int row = char2row[str[0]]; for(string word:words){ int first=char2row[str[0]]; bool flag=true; for(int j=1;j<word.size();j++){ char ch=str[j]; //和第一个字符不是同一行 if(char2row[ch]!=first){ flag=false; break; } //所有字符都是同一行，放入结果数组 if(flag){ res.push_back(str); } } } return res; } };复杂度
n为字符串数组的长度，即单词的个数；m为单词的平均长度
时间复杂度：O(nm)
空间复杂度：O(1)
说明
复杂度没变，但是在不增加空间复杂度的前提下，显著降低了时间复杂度的常数因子——复杂度数量级不变，但实际运行速度大幅提升，这也是哈希表在算法优化中的核心价值。
官方题解
为每一个字母标记行号记录为一个字符串rowIdx，然后用字符-'a'获取到对应索引，那么rowIdx[字符-'a']就是这个字符对所在的行数。这里利用tolower函数将大写字母转换为对应的小写字母更方便，所以对应字符的行数为：rowIdx[tolower(word[0])-'a']。
记录第一个字符的行数first，并用flag表示当前字符串的字符所在行数是否相同，而后遍历每个字符，得到其行数，与first比较，若不等，flag变为false，遍历完一个字符串后，若flag仍为true，说明该字符串的字符都在同一行，将其放入结果字符串数组res。
代码
class Solution { public: vector<string> findWords(vector<string>& words) { vector<string> res;//结果数组 string rowIdx = "12210111011122000010020202"; for(auto&word:words){ bool isValid=true; char idx=rowIdx[tolower(word[0])-'a']; for(int i=0;i<word.size();i++){ if(rowIdx[tolower(word[i])-'a']!=idx){ isValid=false; break; } } if(isValid){ res.emplace_back(word); } } return res; } };我的代码
我自己理解之后写的代码
class Solution { public: vector<string> findWords(vector<string>& words) { vector<string> res;//结果数组 string rowIdx = "12210111011122000010020202"; for(int i=0;i<words.size();i++){ string word=words[i]; //第一个字符的行数 int first=rowIdx[tolower(word[0])-'a']; bool flag=true; for(int j=0;j<word.size();j++){ int cur=rowIdx[tolower(word[j])-'a']; if(cur!=first){ flag=false; break; } } if(flag){ res.push_back(word); } } return res; } };复杂度
L 表示 words 中所有字符串的长度之和；C 表示英文字母的个数，在本题中英文字母的个数为 26
时间复杂度：O(L)
空间复杂度：O(C)
push_back VS emplace_back
emplace_back少了一次拷贝 / 移动，效率更高
