网站维护一次多少钱,北京市工商注册登记网,网站源码在哪,婚纱设计网站模板商城C 栈(stack) 文章目录 C 栈(stack)栈的基本介绍栈的算法运用单调栈实战题LC例题#xff1a;[321. 拼接最大数](https://leetcode.cn/problems/create-maximum-number/)LC例题#xff1a;[316. 去除重复字母](https://leetcode.cn/problems/remove-duplicate-letters/) 栈的基…C 栈(stack) 文章目录 C 栈(stack)栈的基本介绍栈的算法运用单调栈实战题LC例题[321. 拼接最大数](https://leetcode.cn/problems/create-maximum-number/)LC例题[316. 去除重复字母](https://leetcode.cn/problems/remove-duplicate-letters/) 栈的基本介绍
CPP API: stack 一种先进后出FILO的数据结构 定义stack typedef stack_name ; 我们在初始化一个stack时其中的类型也可以为标准库类型以及自定义类型如果想创建一个包含多元素的类型应该如下定义 // 括号中所用的就是
stackpairTreeNode*, int treeStack;函数描述(constructor)该函数用于构造堆栈容器。empty该函数用于测试堆栈是否为空。如果堆栈为空则该函数返回true否则返回false。size该函数返回堆栈容器的大小该大小是堆栈中存储的元素数量的度量。top该函数用于访问堆栈的顶部元素。该元素起着非常重要的作用因为所有插入和删除操作都是在顶部元素上执行的。push该函数用于在堆栈顶部插入新元素。pop该函数用于删除元素堆栈中的元素从顶部删除。emplace该函数用于在当前顶部元素上方的堆栈中插入新元素。swap该函数用于交换引用的两个容器的内容。relational operators非成员函数指定堆栈所需的关系运算符。uses allocator顾名思义非成员函数将分配器用于堆栈。
#include iostream
#include stack
using namespace std;
void newstack(stack int ss)
{stack int sg ss;while (!sg.empty()){cout \t sg.top();sg.pop();}cout \n;
}
int main ()
{stack int newst;newst.push(55);newst.push(44);newst.push(33);newst.push(22);newst.push(11);cout 最新的堆栈是 : ;newstack(newst);cout \n newst.size() : newst.size();cout \n newst.top() : newst.top();cout \n newst.pop() : ;newst.pop();newstack(newst); return 0;
}关于push()和emplace() push()函数接受一个参数该参数是要添加到栈顶的元素的副本。 当调用push()函数时参数会被复制到栈中即使元素是通过移动构造函数构造的也会发生复制。 emplace()函数接受的参数是用于构造栈顶元素的参数列表。 当调用emplace()函数时参数会被直接传递给栈顶元素的构造函数避免了额外的复制操作。因此emplace()通常比push()更高效。 因此主要区别在于push()接受的是元素的值而emplace()接受的是元素构造函数的参数列表。emplace()通常更灵活和高效特别是当元素是通过移动构造函数构造时。
栈的算法运用
单调栈
栈内排序通常满足“单调递增”、“单调递减”即栈中元素具备“单调性”
实战题
LC例题321. 拼接最大数
在这个题目中我们寻找数组的最大子串时运用了单调栈的特性。但并非完全单调以下仅提供寻找最大子串func部分
注意这里的最大子串指的是数组截选出来的子数组中元素相对位置不改变
vectorint MaxSubNums(vectorint nums, int n){// 如果为空不用遍历if (n 0) {return {};}stackint resStack;int pos 0;while (pos nums.size()) {// 余下当前大小 目标大小if ((resStack.size() nums.size() - pos) n) break;// 如果栈为空if (resStack.empty()) {resStack.push(nums[pos]);pos;continue;}// 如果栈满了 且大于栈顶if (resStack.size() n) {if (nums[pos] resStack.top()) {resStack.pop();continue;}else {pos;}}if (resStack.size() n) {// 小于等于直接pushif (nums[pos] resStack.top()) {resStack.push(nums[pos]);pos;}else {resStack.pop();}}}while (resStack.size() n pos nums.size()) {resStack.push(nums[pos]);pos;}vectorint result;while (!resStack.empty()) {result.push_back(resStack.top());resStack.pop();}std::reverse(result.begin(), result.end());return result;}LC例题316. 去除重复字母
题目给你一个字符串 s 请你去除字符串中重复的字母使得每个字母只出现一次。需保证 返回结果的字典序最小要求不能打乱其他字符的相对位置。 解法因为要使结果为字典序最小我们利用单调栈性质使其从底至上为升序非完全
我们需要一个mapstrCount用于记录余下字符串中某字符剩余多少
还需要一个set用于记录栈中已存在哪些元素
遍历字符串入栈规则
首先strCount[cur]–
1、若当前字符cur已在栈中略过
2、若当前字符cur未在栈中
cur stack.top() || stack.empty() 跳到第3步。cur stack.top() 如果栈顶元素之后还会出现弹出循环上述操作直到 栈空 或者 cur stack.top() 或者栈顶元素在之后不再出现结束循环 入栈并在set中记录
遍历完字符串后栈底到栈顶的元素拼起来就是最终答案。
class Solution
{
public:string removeDuplicateLetters(string s){// 判断该字符余下还有多少个unordered_mapchar, int strCount;// 判断栈中是否包含这个元素如果有就不可以pushunordered_setchar inStack;for (auto c : s){strCount[c];}// 单调栈保持从栈底往上升序非完全stackchar strStack;for (auto c : s){// 当前字符剩余个数减1strCount[c]--;// 栈中已有该元素遍历下一个if (inStack.count(c) ! 0)continue;// 如果当前栈不为空 且 当前元素大于栈顶元素且栈顶元素在剩余字符中还会出现while (!strStack.empty() c strStack.top() strCount[strStack.top()] 0){inStack.erase(strStack.top());strStack.pop();}// 入栈strStack.push(c);// 记录该元素已经在栈中出现过inStack.insert(c);}string ans ;while (!strStack.empty()){ans strStack.top() ans;strStack.pop();}return ans;}
};
