共 6 篇文章
传送门 水题，一眼栈 class Solution { public: int calPoints(vector<string>& ops) { stack<int> stk; for (auto el : ops) { if (el[0] == 'C') { if (!stk.empty()) { stk.pop(); } } else if (el[0] == 'D') { int score = stk.top(); stk.push(score * 2); } else if (el[0] == …
传送门 思路 最粗暴的方法就是O(n²)，这题也没卡暴力，可以击败5%混过去，但可以用单调栈来优化。 众所周知，单调栈致力于解决“寻找首个大于(小于)当前位置的值”，要明白单调栈的优势，就要搞清楚它的原理。 常规方法慢在挨个枚举，对每个元素都去一个个的找满足条件的值，那自然是慢的。如果说暴力的思路是“用每个值去找答案”，那单调栈的思路可以形象地理解为“让答案自己去找值”。 就本题而言，单调栈中存的是还没有找到答案的下标，他们自底向上严格上升。在遍历中，如果当前栈顶下标对应的值比nums[i]小，那么nums[i]就是当前值答案，将nums[i]计入ans中并弹出当前下标即完成一次操作。 这样做的正确性是显然地，因为有栈的后入先出特性做保证，当前nums[i]一定最有可能是栈顶元素的答案。 更具体地，因为这题是循环数组，所以需要遍历两次，初始化ans数组为全-1就可以避免最后再来为栈内未出栈的元素赋-1的操作。 代码 ```cpp class Solution { public: vector nextGreaterElements(vector& nums) { const int n = nums.size(); stack stk; vector ans(n, -1); stk.push(0); for (int i = 0; i < n; i++) { while(!stk.empty() && nums[stk.top()] < nums[i]) { …
最近几天LeetCode高强度推送单调栈的题目，以往对这个数据结构的认识都只是停留在肤浅的表层上，看了这些题目后发现这个看似简单的栈结构其实用法很多，也很灵活，于是单独开一篇文章记录学习。 单调栈介绍 顾名思义，单调栈是满足一定单调性的栈结构。现在我们通过模拟实现一个单调递减栈来了解它具体的结构。 有一组数[10,3,7,4,12]。从左到右依次入栈。当且仅当栈为空或入栈元素值小于栈顶元素值时入栈；否则将所有比入栈元素小的元素全部出栈，再进行入栈操作，以确保栈的单调性不被破坏。 10入栈时，栈为空，直接入栈，栈内元素为10。3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。 单调递增的栈反之即可。了解了单调栈的概念，接下来就该撸题了。 单调栈例题 LeetCode-402：移掉K位数字 传送门 思路 题目要计算一个整数去掉k个数位后的最小新整数。最直接的思路就是枚举每一种取法然后维护最小值，但这么做的复杂度显然是指数级，不能这么莽。 考虑O(n)的方法：从左到右遍历num，对每一位数字决定它是否保留，这个操作执行k次即可。那么以什么依据来判断当前数字是该留还是该舍呢？ 假设有两个数字，123a456与123b456，怎么去判断它们谁大谁小呢？显然，a>b时前者大于后者，反之亦然。即，判断两个数大小关系的依据是两者第一个不同的数位大小关系。 根据上面的思路，我们只需要在枚举到每一位的时候去维护一个局部单调递增栈作为答案就好了。为什么是“局部”递增栈呢？因为题目要求我们要去掉k位数位，单调栈在不满足入栈条件的情况下会一直弹出栈内元素直到满足入栈条件，我们显然不能让它把答案全弹出去，所以当不能再弹的时候(即(n-k)-ans.size()>=n-i时)就继续去枚举下一位数位。 代码 ```cpp class Solution { public: string removeKdigits(string num, int k) { int n = num.size(); string ans = ""; if(n == k) return "0"; if(k == 0) return num; for(int …
传送门 题目意思很好理解，就是维护一个单调栈。 ```cpp class Solution { public: vector mostCompetitive(vector& nums, int k) { int n = nums.size(); if(k == n) return nums; stack st; for(int i = 0; i < n; i++) { while(!st.empty() && st.top() > nums[i] && k - st.size() < n - …
传送门 题目大意 给定一个由10种字符(p,q,r,s,t,N,K,A,C,E)组成的逻辑表达式，其中pqrst为逻辑变量，NKACE为逻辑运算符，他们的含义分别是 K==and：x && yN==not：!xA==or：x || yC==implies：(!x)||y E==equals：x==y 要求判断这个逻辑表达式是否为重言式，如果是就输出tautology，否则输出not 思路 根据题设，我们不难判断，单目运算符一定在整个字符串的后半部分，双目运算符一定在整个字符串的前半部分。例如ApNp，它应该被判为A(p,N(p))，所以上述结论的正确性是显然的。那么就可以像常规的表达式计算一样，从尾部压入栈，然后弹一个计算一个。 因为只有5个逻辑变量，所以最多只会有2^5=32种情况，依次枚举就好。 代码 我的写法 五重循环枚举每一位，最内层去枚举长度。 ```cpp #include #include #include #include using namespace std; string str; bool input(stack& sta, char ss, int p, int q, int r, int s, int t) …
传送门 题目大意 如果通过插入 "+"和 "1 "可以从中得到一个形式完整的数学表达式，那么一个带括号的序列 就被称为正确。例如，"(())()"、"() "和"(()())) "等序列是正确的，而")("、"(()) "和"(()))("则不正确。 老师给德米特里的班级布置了一个非常奇怪的任务：她要求每个学生想出一个任意长度的序 列，只由开头和结尾的括号组成。之后，所有学生轮流说出自己想出的序列。轮到迪马时，他突然发现，所有同学都得到了正确的括号序列，而他是否得到了正确的括号序列，他不知道。 迪马现在怀疑自己只是漏掉了任务书中的 "正确 "二字，所以现在他想通过稍微修改自己的序 列来挽救局面。更准确地说，他可以任意次数（可能是零）地执行重排序操作。 重排序操作包括选择序列中任意一个连续的子串，然后以任意的方式对其中的所有字符进行重 排序。这种操作需要l纳秒，其中l是被重新排序的子段的长度。很容易看出，重新排序操作并 不会改变开括号和收括号的数量。例如对于"))(("，他可以选择子串")("，然后进行重排 序")()("(这个操作需要2纳秒)。 由于Dima很快就要回答，他想尽快让自己的序列正确。帮助他做到这一点，或者确定这是不可能的。 输入输出 输入 第一行包含一个整数n(1≤n≤10e6)表示序列的长度。 第二行包含长度为n的字符串，仅由字符"("和") "组成。 输出 打印一个整数：使序列正确的最小纳秒数，如果不可能做到，则打印"-1"。 难度不大的栈括号，遇到左括号就压进去，右括号弹，如果栈不空就输出-1，否则输出答案。 ```cpp #include using namespace std; typedef long long ll; …