传送门 拿到这题第一思路肯定是n³直接暴，但肯定会超时，事实上定一动二的n²都能超，那么根据传统优化思路，只枚举一个就行。 根据枚举位置的不同，有两种不一样的思路。 方法一：有序集合(枚举k) 思路 枚举j，即寻找一个满足“i<j<k且nums[i]<nums[k]<nums[j]”的j。因为最左侧的i同时满足下标最小与值最小，所以可以用一个变量来记录当前最小值，也就省去了枚举i的开销。 在这同时，用一个有序集合来维护自当前枚举的位置到nums尾部的序列，它的作用是从其中找k。 在枚举时，没枚举到一个j，就从该有序集合中找到“第一个大于nums[i](也就是上文提到过的'当前最小值')的值”，根据贪心思想，它就最可能是满足条件的k。如果此时的nums[j]大于该值，则可以直接返回true；否则维护nums[i]的最小性，维护该有序集合的长度，再进行下一轮枚举，直到尾部。 代码 ```cpp class Solution { public: bool find132pattern(vector& nums) { // 左区间最小值 int left = nums[0]; // 右区间序列 multiset right; const int n = nums.size(); if (n < 3) { return false; } // 右维护 for …
传送门 思路 最粗暴的方法就是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 - …