目錄

• • 單調(diào)棧知識(shí)
  • 402. 移掉K位數(shù)字
  • 1673. 找出最具競(jìng)爭(zhēng)力的子序列
  • 316. 去除重復(fù)字母（1081. 不同字符的最小子序列）
  • 321. 拼接最大數(shù)

單調(diào)棧知識(shí)

單調(diào)棧就是一個(gè)內(nèi)部元素有序的棧（大->小 or 小->大），但是只用到它的一端。
核心代碼：摘自C++ | 圖解算法 | 這個(gè)單調(diào)棧不一般！

insert x while (!sta.empty() && sta.top()<x)sta.pop() sta.push(x)

單調(diào)棧只能在棧頂操作.
單調(diào)棧可以解決的問(wèn)題：
1、找到一個(gè)序列的字典序最小的序列(序列元素位置不可移動(dòng))
2、最基礎(chǔ)的應(yīng)用就是給定一組數(shù)，針對(duì)每個(gè)數(shù)，尋找它和它右邊第一個(gè)比它大的數(shù)之間有多少個(gè)數(shù)。
3、給定一序列，尋找某一子序列，使得子序列中的最小值乘以子序列的長(zhǎng)度最大。
4、給定一序列，尋找某一子序列，使得子序列中的最小值乘以子序列所有元素和最大。

參考有關(guān)文章：
一招吃遍力扣四道題，媽媽再也不用擔(dān)心我被套路啦～
單調(diào)棧的介紹以及一些基本性質(zhì)
下面是刷題代碼：

402. 移掉K位數(shù)字

402. 移掉K位數(shù)字

class Solution { public:string removeKdigits(string num, int k) {vector<char> 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--;}//否則，進(jìn)行st.push_back(num[i]);}//考慮到所有情況之后，還有k剩余，但是此時(shí)字符是單調(diào)遞減的，需要將末尾的字符進(jìn)行去除while(k > 0){st.pop_back();k--;}//去除前導(dǎo)0int j;for(j=0; j < st.size(); j++){if(st[j] != '0') break;}for(int i = j; i < st.size() ; i++){result += st[i];}//如果最后結(jié)果為空，返回0即可if(result.size() == 0) return "0";return result;} };

1673. 找出最具競(jìng)爭(zhēng)力的子序列

1673. 找出最具競(jìng)爭(zhēng)力的子序列

class Solution { public:vector<int> mostCompetitive(vector<int>& nums, int k) {vector<int> 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--;}//否則，進(jìn)行st.push_back(nums[i]);}while(remain > 0){st.pop_back();remain--;}return st;} };

316. 去除重復(fù)字母（1081. 不同字符的最小子序列）

316. 去除重復(fù)字母
錯(cuò)誤代碼，沒(méi)考慮包含text中所有不同的字符一次。
所以出現(xiàn)結(jié)果只是不含相同字符的字典序最小的子序列

class Solution { public:string smallestSubsequence(string s) {vector<char > st;int hash[26]={0};for(int i = 0; i < s.size(); i++){//如果元素大于棧頂元素，并且這個(gè)元素沒(méi)有出現(xiàn)過(guò)，則插入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() <<endl;}else{//如果這個(gè)元素小于棧頂元素，并且這個(gè)元素沒(méi)有出現(xiàn)過(guò)，那么我們就刪除棧頂元素，插入這個(gè)元素while(st.size() > 0 && s[i] < st.back() && hash[s[i]-'a'] == 0){//被刪除的棧頂元素對(duì)應(yīng)的hash也需要清除hash[st.back()-'a'] = 0;st.pop_back();//cout << st.back() <<endl;}st.push_back(s[i]);hash[s[i]-'a'] = 1;}//如果這個(gè)元素已經(jīng)出現(xiàn)過(guò)了，那么不做任何操作}string result;//將vector元素轉(zhuǎn)化為stringfor(int i = 0; i < st.size(); i++){result += st[i];}return result;} };

正確代碼：

class Solution { public:string smallestSubsequence(string s) {vector<char > 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();}elsebreak;}st.push_back(s[i]);hash[s[i] - 'a'] = 1;}string result;//將vector元素轉(zhuǎn)化為stringfor(int i = 0; i < st.size(); i++){result += st[i];}return result;} };

321. 拼接最大數(shù)

321. 拼接最大數(shù)
1、將k拆分為x，y，格子找nums1，nums2對(duì)應(yīng)的x，y長(zhǎng)度的最有競(jìng)爭(zhēng)力的子序列(如果x,y大于任意數(shù)組長(zhǎng)度，則pass這個(gè)解法)
2、對(duì)x+y=k的對(duì)應(yīng)的兩個(gè)子序列進(jìn)行合并
3、對(duì)合并后的每個(gè)子序列，進(jìn)行比較，找到最終結(jié)果.
4、補(bǔ)充一下比較的規(guī)則，從序列的第一個(gè)開(kāi)始比較，返回對(duì)應(yīng)位的較小的序列。
5、合并的規(guī)則也需要注意，并不能用簡(jiǎn)單的雙指針比較,需要注意到當(dāng)前數(shù)相同的情況，還要往后比較，才能選擇出我們我們送入的數(shù)
哪個(gè)大取哪個(gè)，當(dāng)前位置相同就繼續(xù)比較下一位。這個(gè)比較的過(guò)程和比較函數(shù)有重復(fù)的操作，所以我們需要將比較函數(shù)做一下修改，保證在合并比較的時(shí)候也能使用。

compare函數(shù)從兩個(gè)index開(kāi)始對(duì)比，如果nums1順位大于nums2，返回值大于0。
有個(gè)序列是另一個(gè)序列的子序列，這時(shí)我們選擇較長(zhǎng)的序列。

int compare(vector<int>& nums1,int index1, vector<int>& 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++;}//如果比較到這個(gè)時(shí)候還沒(méi)結(jié)果，說(shuō)明有個(gè)序列是另一個(gè)序列的子序列，這時(shí)我們選擇較長(zhǎng)的序列return (n - index1) - (m - index2);}

合并函數(shù)
每次將順位比較中較大的nums中對(duì)應(yīng)的index送入result數(shù)組中。

vector<int> merge(vector<int>& nums1, vector<int>& nums2){int x = nums1.size();int y = nums2.size();vector<int> result(x + y,0);int index1 = 0, index2 = 0;if(x == 0) return nums2;else if( y == 0) return nums1;//此時(shí)需要進(jìn)行比較,從頭開(kāi)始比較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：找出最具競(jìng)爭(zhēng)力的子序列/*給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)正整數(shù) k ，返回長(zhǎng)度為 k 且最具 競(jìng)爭(zhēng)力 的 nums 子序列。*/vector<int> mostCompetitive(vector<int>& nums, int k) {vector<int> 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--;}//否則，進(jìn)行st.push_back(nums[i]);}while(remain > 0){st.pop_back();remain--;}return st;}vector<int> merge(vector<int>& nums1, vector<int>& nums2){int x = nums1.size();int y = nums2.size();vector<int> result(x + y,0);int index1 = 0, index2 = 0;if(x == 0) return nums2;else if( y == 0) return nums1;//此時(shí)需要進(jìn)行比較,從頭開(kāi)始比較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<int>& nums1,int index1, vector<int>& 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++;}//如果比較到這個(gè)時(shí)候還沒(méi)結(jié)果，說(shuō)明有個(gè)序列是另一個(gè)序列的子序列，這時(shí)我們選擇較長(zhǎng)的序列return (n - index1) - (m - index2);} public:vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {int n = nums1.size();int m = nums2.size();//用來(lái)放最終結(jié)果vector<int> maxSubsequence(k,0);vector<int> cur_maxSubsequence(k,0);//【1】將k拆分為x，y，格子找nums1，nums2對(duì)應(yīng)的x，y長(zhǎng)度的最有競(jìng)爭(zhēng)力的子序列for(int x = 0; x <= n; x++){int y = k - x;//如果x,y大于任意數(shù)組長(zhǎng)度，則pass這個(gè)解法)if(y > m || y < 0 || x < 0 || x > n) continue;vector<int> maxSubsequence1 = mostCompetitive(nums1,x);vector<int> maxSubsequence2 = mostCompetitive(nums2,y);//【2】對(duì)x+y=k的對(duì)應(yīng)的兩個(gè)子序列進(jìn)行合并cur_maxSubsequence = merge(maxSubsequence1,maxSubsequence2);//【3】if(compare(cur_maxSubsequence,0,maxSubsequence,0) > 0)maxSubsequence = cur_maxSubsequence;}return maxSubsequence;} };

總結(jié)

以上是生活随笔為你收集整理的单调栈 leetcode整理（一）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。