单调栈 leetcode整理（一）

单调栈 leetcode整理（一）

目录​​单调栈知识​​​​402. 移掉K位数字​​​​1673. 找出最具竞争力的子序列​​​​316. 去除重复字母（1081. 不同字符的最小子序列）​​​​321. 拼接最大数​​

单调栈知识

单调栈就是一个内部元素有序的栈（大->小 or 小->大），但是只用到它的一端。 核心代码：​​​摘自C++ | 图解算法 | 这个单调栈不一般！​​

insert xwhile (!sta.empty() && sta.top()

单调栈只能在栈顶操作. 单调栈可以解决的问题： 1、找到一个序列的字典序最小的序列(序列元素位置不可移动) 2、最基础的应用就是给定一组数，针对每个数，寻找它和它右边第一个比它大的数之间有多少个数。 3、给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列的长度最大。 4、给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列所有元素和最大。

参考有关文章：​​​一招吃遍力扣四道题，妈妈再也不用担心我被套路啦～​​​​单调栈的介绍以及一些基本性质​​ 下面是刷题代码：

402. 移掉K位数字

​​402. 移掉K位数字​​

class Solution {public: string removeKdigits(string num, int k) { vector st; string result; for(int i = 0; i < num.size(); i++) { while(st.size() > 0 && st.back() > num[i] && k > 0) { st.pop_back(); k--; } //否则，进行 st.push_back(num[i]); } //考虑到所有情况之后，还有k剩余，但是此时字符是单调递减的，需要将末尾的字符进行去除 while(k > 0) { st.pop_back(); k--; } //去除前导0 int j; for(j=0; j < st.size(); j++) { if(st[j] != '0') break; } for(int i = j; i < st.size() ; i++) { result += st[i]; } //如果最后结果为空，返回0即可 if(result.size() == 0) return "0"; return result; }};

1673. 找出最具竞争力的子序列

​​1673. 找出最具竞争力的子序列​​

class Solution {public: vector mostCompetitive(vector& nums, int k) { vector st; int remain = nums.size() - k; for(int i = 0; i < nums.size(); i++) { while(st.size() > 0 && st.back() > nums[i] && remain > 0) { st.pop_back(); remain--; } //否则，进行 st.push_back(nums[i]); } while(remain > 0) { st.pop_back(); remain--; } return st; }};

316. 去除重复字母（1081. 不同字符的最小子序列）

​​316. 去除重复字母​​​ 错误代码，没考虑包含text中所有不同的字符一次。 所以出现结果只是不含相同字符的字典序最小的子序列

class Solution {public: string smallestSubsequence(string s) { vector st; int hash[26]={0}; for(int i = 0; i < s.size(); i++) { //如果元素大于栈顶元素，并且这个元素没有出现过，则插入 if(st.size() == 0 || (st.back() < s[i] && hash[s[i]-'a'] == 0)) { st.push_back(s[i]); hash[s[i]-'a'] = 1; //cout << st.back() < 0 && s[i] < st.back() && hash[s[i]-'a'] == 0) { //被删除的栈顶元素对应的hash也需要清除 hash[st.back()-'a'] = 0; st.pop_back(); //cout << st.back() <

正确代码：

class Solution {public: string smallestSubsequence(string s) { vector st; int hash[26]={0}; int cnt_s[26]={0}; for(int i = 0; i < s.size() ; i++) { cnt_s[s[i] - 'a'] += 1; } for(int i = 0; i < s.size(); i++) { cnt_s[s[i] - 'a'] -= 1; if(hash[s[i] - 'a'] == 1) continue; while(st.size() > 0) { if(st.back() > s[i] && cnt_s[st.back() - 'a'] > 0) { hash[st.back() - 'a'] = 0; st.pop_back(); } else break; } st.push_back(s[i]); hash[s[i] - 'a'] = 1; } string result; //将vector元素转化为string for(int i = 0; i < st.size(); i++) { result += st[i]; } return result; }};

321. 拼接最大数

​​321. 拼接最大数​​​ 1、将k拆分为x，y，格子找nums1，nums2对应的x，y长度的最有竞争力的子序列(如果x,y大于任意数组长度，则pass这个解法) 2、对x+y=k的对应的两个子序列进行合并 3、对合并后的每个子序列，进行比较，找到最终结果. 4、补充一下比较的规则，从序列的第一个开始比较，返回对应位的较小的序列。 5、合并的规则也需要注意，并不能用简单的双指针比较,需要注意到当前数相同的情况，还要往后比较，才能选择出我们我们送入的数 哪个大取哪个，当前位置相同就继续比较下一位。这个比较的过程和比较函数有重复的操作，所以我们需要将比较函数做一下修改，保证在合并比较的时候也能使用。

compare函数从两个index开始对比，如果nums1顺位大于nums2，返回值大于0。 有个序列是另一个序列的子序列，这时我们选择较长的序列。

int compare(vector& nums1,int index1, vector& nums2,int index2) { int n = nums1.size(); int m = nums2.size(); while(index1 < n && index2 < m) { int difference = nums1[index1] - nums2[index2]; //如果不相同，返回nums1与nums2的差值 if (difference != 0) { return difference; } //如果相同，比较下一位 index1++; index2++; } //如果比较到这个时候还没结果，说明有个序列是另一个序列的子序列，这时我们选择较长的序列 return (n - index1) - (m - index2); }

合并函数 每次将顺位比较中较大的nums中对应的index送入result数组中。

vector merge(vector& nums1, vector& nums2) { int x = nums1.size(); int y = nums2.size(); vector result(x + y,0); int index1 = 0, index2 = 0; if(x == 0) return nums2; else if( y == 0) return nums1; //此时需要进行比较,从头开始比较 for(int i = 0; i < x + y; i++) { if(compare(nums1,index1,nums2,index2) > 0) { result[i] = nums1[index1]; index1++; } else { result[i] = nums2[index2]; index2++; } } return result; }

最终代码：

class Solution {private: //function1：找出最具竞争力的子序列 /*给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。*/ vector mostCompetitive(vector& nums, int k) { vector st; int remain = nums.size() - k; for(int i = 0; i < nums.size(); i++) { while(st.size() > 0 && st.back() < nums[i] && remain > 0) { st.pop_back(); remain--; } //否则，进行 st.push_back(nums[i]); } while(remain > 0) { st.pop_back(); remain--; } return st; } vector merge(vector& nums1, vector& nums2) { int x = nums1.size(); int y = nums2.size(); vector result(x + y,0); int index1 = 0, index2 = 0; if(x == 0) return nums2; else if( y == 0) return nums1; //此时需要进行比较,从头开始比较 for(int i = 0; i < x + y; i++) { if(compare(nums1,index1,nums2,index2) > 0) { result[i] = nums1[index1]; index1++; } else { result[i] = nums2[index2]; index2++; } } return result; } int compare(vector& nums1,int index1, vector& nums2,int index2) { int n = nums1.size(); int m = nums2.size(); while(index1 < n && index2 < m) { int difference = nums1[index1] - nums2[index2]; //如果不相同，返回nums1与nums2的差值 if (difference != 0) { return difference; } //如果相同，比较下一位 index1++; index2++; } //如果比较到这个时候还没结果，说明有个序列是另一个序列的子序列，这时我们选择较长的序列 return (n - index1) - (m - index2); }public: vector maxNumber(vector& nums1, vector& nums2, int k) { int n = nums1.size(); int m = nums2.size(); //用来放最终结果 vector maxSubsequence(k,0); vector cur_maxSubsequence(k,0); //【1】将k拆分为x，y，格子找nums1，nums2对应的x，y长度的最有竞争力的子序列 for(int x = 0; x <= n; x++) { int y = k - x; //如果x,y大于任意数组长度，则pass这个解法) if(y > m || y < 0 || x < 0 || x > n) continue; vector maxSubsequence1 = mostCompetitive(nums1,x); vector maxSubsequence2 = mostCompetitive(nums2,y); //【2】对x+y=k的对应的两个子序列进行合并 cur_maxSubsequence = merge(maxSubsequence1,maxSubsequence2); //【3】 if(compare(cur_maxSubsequence,0,maxSubsequence,0) > 0) maxSubsequence = cur_maxSubsequence; } return maxSubsequence; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。