代码摘自lau大佬,感恩哈哈!
1.lc316 去除重复字母
题目:https://leetcode.cn/problems/remove-duplicate-letters/
栈和贪心思想
这个题我们开两个哈希表,一个记录是否出现过,一个记录这个字母最后一次出现的地方在哪里?
最头到尾遍历字符串,存下每个字符最终出现的位置
然后在遍历一遍,如果这个字符之前出现过,跳出本次循环;
当栈不空的时候并且入栈的栈顶元素他的字典序大于当前要入栈的元素
并且栈顶元素最后一次出现的位置大于当前的要入栈的位置i(说明不是最后一个位置,后面还有)
满足这三个条件就可以标记成未出现,同时弹出当前元素;
加入当前要入栈的元素
入栈后,把这个元素标记为true;
class Solution {
public:
string removeDuplicateLetters(string s) {
string stk; // 答案字符串
unordered_map<char, bool> ins; // 记录每个字母是不是在栈中出现过in stack
unordered_map<char, int> last; // 记录每个字母最后一次出现的位置,用来判断当前字母是不是最后一次出现的
// 先计算一下每个字母最后一次出现的位置
for (int i = 0; i < s.size(); i ++ ) last[s[i]] = i;
// 从前往后枚举每个字母
for (int i = 0; i < s.size(); i ++ ) {
auto c = s[i];
// 如果当前字母已经在字符串里了,那就直接跳过
if (ins[c]) continue;
// 只要栈顶是比当前字母字典序大的,并且是可以删去的(不是最后一次出现),那么就把它删除掉
while (stk.size() && stk.back() > c && last[stk.back()] > i) {
// 删去的字母标记为在stk里不存在
ins[stk.back()] = false;
stk.pop_back();
}
stk += c;
ins[c] = true;
}
return stk;
}
};
2.lc402 移除k位数字
https://leetcode.cn/problems/remove-k-digits/
前i-1位都弄好了,第i位来了之后
已经进入数组的数组最后一个元素如果大于要进数组的当前元素的话,那么就要更新了!保证前面留的数字大小越小越好!
class Solution {
public:
string removeKdigits(string num, int k) {
if (k > num.size()) return "0";
string res;
for (auto c: num) {
// 当还可以删的时候,并且比答案里的最后一位要小,那就把它删除掉
while (k && res.size() && res.back() > c) {
k -- ;
res.pop_back();
}
res += c;
}
// 如果还没删完,就从后往前删
while (k -- ) res.pop_back();
// 去除前导0
k = 0;
while (k < res.size() && res[k] == '0') k ++ ;
res = res.substr(k);
if (res.empty()) return "0";
return res;
}
};
3.lc496 下一个更大元素 I
https://leetcode.cn/problems/next-greater-element-i/
求每一个数后面比他大的第一个数
用单调栈可以在o(n)的时间内完成
先弄nums2数组,求每个数右边第一个比他大的数,将他们标记出来
然后遍历nums1,找出nums1在nums2的位置
这里stk还是存储角标
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int>stk;
vector<int>q(nums2.size());
for(int i=nums2.size()-1;i>=0;i--)
{
while(stk.size() && nums2[i]>=nums2[stk.top()]) stk.pop();
if(stk.size()) q[i]=stk.top();
else q[i]=-1;
stk.push(i);
}
unordered_map<int,int>hash;
for(int i=0;i<nums2.size();i++) hash[nums2[i]]=i;
vector<int>res;
for(auto x:nums1)
{
if(q[hash[x]]==-1) res.push_back(-1);
else res.push_back(nums2[q[hash[x]]]);
}
return res;
}
};
4.lc503 下一个更大元素 II
https://leetcode.cn/problems/next-greater-element-ii/
环形
技巧:破环成连,复制一个数组在原数组后面;
长度是2n的数组,求第一个后面比他大元素;
stk记录的数值
如题解所说,滑动窗口的题一般下标,其他可以用数值
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.end(), nums.begin(), nums.end());
// 单调栈,里面直接存nums数组的值(对于单调队列有的时候存的是下标,特别是滑动窗口要用下标判断有没有滑出去)
stack<int> stk;
vector<int> res(n);
// 因为是要求后面的第一个满足要求的元素,所以从后往前枚举
for (int i = n * 2 - 1; i >= 0; i -- ) {
int x = nums[i];
while (stk.size() && x >= stk.top()) // 因为要求是比x大,所以<=x的都弹出去
stk.pop();
// 只在i在原来数组的0~n-1范围里的时候记录答案
if (i < n) {
if (stk.empty()) res[i] = -1;
else res[i] = stk.top();
}
stk.push(x);
}
return res;
}
};
5.lc 321 拼接最大数
https://leetcode.cn/problems/create-maximum-number/
题目要求在两个数组里面选k个数,然后保持它们原来在各自的数组中的顺序合并成一个数,要让这个数字最大。
枚举第一个数组里选i个,第二个数组里面选k-i个,要让整体是最大的,那么从长为n的第一个数组中选的i个数一定是字典序最大的,而且从长为m的第二个数组中选的k-i个数也一定是字典序最大的。
所以迫切要解决的问题就是这样几个子问题:
1.从长度为m的数组里面选k个数,让它的字典序最大,怎么选。
2.按顺序合并两个数组,字典序最大
第一个问题可以准备一个栈,在数组中遍历的时候元素和栈顶比较,来考虑删除栈顶元素。
第二个问题是用两个指针分别指向两个数组的开头,然后往后移动的过程中判断一下,如果两个指针所指向的数字不一样大,那么就把大的那个落下来,如果两个指针所指向的数字一样大,那么要while比较后面的,谁大就落谁,这样后面的大数才能先落出来。
作者:LauZyHou
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n=nums1.size(),m=nums2.size();
vector<int>res(k,INT_MIN);
for(int i=max(0,k-m);i<=min(k,n);i++)
{
auto a=maxArray(nums1,i);
auto b=maxArray(nums2,k-i);
auto c=merge(a,b);
res=max(res,c);
}
return res;
}
vector<int> merge(vector<int>&a,vector<int>&b)
{
vector<int>c;
while(a.size() && b.size())
{
if(a>b) c.push_back(a[0]),a.erase(a.begin());
else c.push_back(b[0]),b.erase(b.begin());
}
while(a.size()) c.push_back(a[0]),a.erase(a.begin());
while(b.size()) c.push_back(b[0]),b.erase(b.begin());
return c;
}
vector<int>maxArray(vector<int>&nums,int k)
{
int n=nums.size();
vector<int>res(k);
for(int i=0,j=0;i<n;i++)
{
int x=nums[i];
while(j && res[j-1]<x && j+n-i>k) j--;
if(j<k) res[j++]=x;
}
return res;
}
};