七. 貪心算法

• 題目分類(lèi) 題目編號(hào)
• 數(shù)組與貪心算法 605、121、122、561、455、575、135、409、621、179、56、57、228、452、435、646、406、48、169、215、75、324、517、649、678、420
• 子數(shù)組與貪心算法 53、134、581、152
• 子序列與貪心算法 334、376、659
• 數(shù)字與貪心 343
• 單調(diào)棧法 496、503、456、316、402、321、84、85

1. 605 種花問(wèn)題

解法：貪心算法

我們直接遍歷數(shù)組flowerbed，對(duì)于每個(gè)位置 iii，如果flowerbed[i]=0，并且其左右相鄰位置都為 0，則我們可以在該位置種花，否則不能。最后我們統(tǒng)計(jì)可以種下的花的數(shù)量，如果其不小于 n，則返回 true，否則返回 false。

代碼：

class Solution {
public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int len=flowerbed.size();if(n==0)return true;for(int i=0;i<len;i++){if(i==0&&flowerbed[i]==0){if(len==1||flowerbed[i+1]==0){n--;flowerbed[i]=1;}}else if(i==len-1&&flowerbed[i]==0){if(flowerbed[i-1]==0){n--;flowerbed[i]=1;}}else{if(flowerbed[i]==0&&flowerbed[i-1]==0&&flowerbed[i+1]==0){n--;flowerbed[i]=1;}}if(n==0)return true;}return false;}
};

注意有種簡(jiǎn)潔的代碼描述方式，比上述代碼來(lái)的簡(jiǎn)潔的多

class Solution {
public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int m = flowerbed.size();for (int i = 0; i < m; ++i) {int l = i == 0 ? 0 : flowerbed[i - 1];int r = i == m - 1 ? 0 : flowerbed[i + 1];if (l + flowerbed[i] + r == 0) {flowerbed[i] = 1;--n;}}return n <= 0;}
};

時(shí)間復(fù)雜度：O(n)，其中 n 是數(shù)組 flowerbed的長(zhǎng)度。只需要遍歷數(shù)組一次。

空間復(fù)雜度: O(1)。

2. 121 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)

解法1：一次遍歷

假設(shè)給定的數(shù)組為：[7, 1, 5, 3, 6, 4]

我們來(lái)假設(shè)自己來(lái)購(gòu)買(mǎi)股票。隨著時(shí)間的推移，每天我們都可以選擇出售股票與否。那么，假設(shè)在第 i 天，如果我們要在今天賣(mài)股票，那么我們能賺多少錢(qián)呢？

顯然，如果我們真的在買(mǎi)賣(mài)股票，我們肯定會(huì)想：如果我是在歷史最低點(diǎn)買(mǎi)的股票就好了，在題目中，我們只要用一個(gè)變量記錄一個(gè)歷史最低價(jià)格 minPrice，我們就可以假設(shè)自己的股票是在那天買(mǎi)的。那么我們?cè)诘?i 天賣(mài)出股票能得到的利潤(rùn)就是 prices[i] - minPrice。

因此，我們只需要遍歷價(jià)格數(shù)組一遍，記錄歷史最低點(diǎn)，然后在每一天考慮這么一個(gè)問(wèn)題：如果我是在歷史最低點(diǎn)買(mǎi)進(jìn)的，那么我今天賣(mài)出能賺多少錢(qián)？當(dāng)考慮完所有天數(shù)之時(shí)，我們就得到了最好的答案。

代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {int len=prices.size();if(len<2)return 0;int minPrice=prices[0],maxProfit=0;for(int p:prices){maxProfit=max(maxProfit,p-minPrice);minPrice=min(p,minPrice);}return maxProfit;}
};

時(shí)間復(fù)雜度：O(n) 只遍歷了一次

空間復(fù)雜度：O(1) 只使用了常量個(gè)變量。

解法2: 動(dòng)態(tài)規(guī)劃

思路：題目只問(wèn)最大利潤(rùn)，沒(méi)有問(wèn)這幾天具體哪一天買(mǎi)、哪一天賣(mài)，因此可以考慮使用 動(dòng)態(tài)規(guī)劃 的方法來(lái)解決。

買(mǎi)賣(mài)股票有約束，根據(jù)題目意思，有以下兩個(gè)約束條件：

條件 1：你不能在買(mǎi)入股票前賣(mài)出股票；
條件 2：最多只允許完成一筆交易。
因此 當(dāng)天是否持股 是一個(gè)很重要的因素，而當(dāng)前是否持股和昨天是否持股有關(guān)系，為此我們需要把 是否持股 設(shè)計(jì)到狀態(tài)數(shù)組中。

dp[i][j]：下標(biāo)為 i 這一天結(jié)束的時(shí)候，手上持股狀態(tài)為 j 時(shí)，我們持有的現(xiàn)金數(shù)。換種說(shuō)法：dp[i][j] 表示天數(shù) [0, i] 區(qū)間里，下標(biāo) i 這一天狀態(tài)為 j 的時(shí)候能夠獲得的最大利潤(rùn)。其中：

j = 0，表示當(dāng)前不持股；
j = 1，表示當(dāng)前持股。

注意：下標(biāo)為 i 的這一天的計(jì)算結(jié)果包含了區(qū)間 [0, i] 所有的信息，因此最后輸出 dp[len - 1][0]。

使用「現(xiàn)金數(shù)」這個(gè)說(shuō)法主要是為了體現(xiàn) 買(mǎi)入股票手上的現(xiàn)金數(shù)減少，賣(mài)出股票手上的現(xiàn)金數(shù)增加 這個(gè)事實(shí)；
「現(xiàn)金數(shù)」等價(jià)于題目中說(shuō)的「利潤(rùn)」，即先買(mǎi)入這只股票，后買(mǎi)入這只股票的差價(jià)；

推導(dǎo)狀態(tài)轉(zhuǎn)移方程：

dp[i][0]：規(guī)定了今天不持股，有以下兩種情況：

• 昨天不持股，今天什么都不做；

• 昨天持股，今天賣(mài)出股票（現(xiàn)金數(shù)增加），

dp[i][1]：規(guī)定了今天持股，有以下兩種情況：

• 昨天持股，今天什么都不做（現(xiàn)金數(shù)與昨天一樣）；
• 昨天不持股，今天買(mǎi)入股票（注意：只允許交易一次，因此手上的現(xiàn)金數(shù)就是當(dāng)天的股價(jià)的相反數(shù)）。

代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {int len=prices.size();if(len<2)return 0;int dp[len][2];// dp[i][0] 下標(biāo)為 i 這天結(jié)束的時(shí)候，不持股，手上擁有的現(xiàn)金數(shù)// dp[i][1] 下標(biāo)為 i 這天結(jié)束的時(shí)候，持股，手上擁有的現(xiàn)金數(shù)dp[0][0]=0;dp[0][1]=-prices[0];for(int i=1;i<len;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);dp[i][1]=max(dp[i-1][1],-prices[i]);}return dp[len-1][0];}
};

• 時(shí)間復(fù)雜度：O(N)，遍歷股價(jià)數(shù)組可以得到最優(yōu)解；
• 空間復(fù)雜度：O(N)，狀態(tài)數(shù)組的長(zhǎng)度為 N。

3. 561 數(shù)組拆分

解法：排序

我們先對(duì)數(shù)組進(jìn)行排序。由于每?jī)蓚€(gè)數(shù)，我們只能選擇當(dāng)前小的一個(gè)進(jìn)行累加。因此我們猜想應(yīng)該從第一個(gè)位置進(jìn)行選擇，然后隔一步選擇下一個(gè)數(shù)。這樣形成的序列的求和值最大。

我們用反證法來(lái)證明下，為什么這樣選擇的序列的求和值一定是最大的：

猜想：對(duì)數(shù)組進(jìn)行排序，從第一個(gè)位置進(jìn)行選擇，然后隔一步選擇下一個(gè)數(shù)。這樣形成的序列的求和值最大（下圖黑標(biāo)，代表當(dāng)前被選擇的數(shù)字）。

之所以我們能這么選擇，是因?yàn)槊恳粋€(gè)被選擇的數(shù)的「下一位位置」都對(duì)應(yīng)著一個(gè)「大于等于」當(dāng)前數(shù)的值（假設(shè)位置為 k ），使得當(dāng)前數(shù)在 min(a,b) 關(guān)系中能被選擇（下圖紅標(biāo)，代表保證前面一個(gè)黑標(biāo)能夠被選擇的輔助數(shù)）。

假如我們這樣選擇的序列求和不是最大值，那么說(shuō)明至少我們有一個(gè)值選錯(cuò)了，應(yīng)該選擇更大的數(shù)才對(duì)。

那么意味著我們「某一位置」的黑標(biāo)應(yīng)該從當(dāng)前位置指向更后的位置。

PS. 因?yàn)橐獫M足 min(a, b) 的數(shù)才會(huì)被累加，因此每一個(gè)紅標(biāo)右移（變大）必然導(dǎo)致原本所對(duì)應(yīng)的黑標(biāo)發(fā)生「同樣程度 或 不同程度」的右移（變大）

這會(huì)導(dǎo)致我們所有的紅標(biāo)黑標(biāo)同時(shí)往后平移。

最終會(huì)導(dǎo)致我們最后一個(gè)黑標(biāo)出現(xiàn)在最后一位，這時(shí)候最后一位黑標(biāo)不得不與我們第 k 個(gè)位置的數(shù)形成一對(duì)。

我們看看這是求和序列的變化（ k 位置前的求和項(xiàng)沒(méi)有發(fā)生變化，我們從 k 位置開(kāi)始分析）：

原答案 = nums[k] + nums[k + 2] + … + nums[n - 1]
調(diào)整后答案 = nums[k + 1] + nums[k + 3] + … + nums[n - 2] + min(nums[n], nums[k])
由于 min(nums[n], nums[k]) 中必然是 nums[k] 被選擇。因此：
調(diào)整后答案 = nums[k] + nums[k + 1] + nums[k + 3] + … + nums[n - 2]
顯然從原答案的每一項(xiàng)都「大于等于」調(diào)整后答案的每一項(xiàng)，因此不可能在「假想序列」中通過(guò)選擇別的更大的數(shù)得到更優(yōu)解，假想得證。

代碼：

class Solution {
public:int arrayPairSum(vector<int>& nums) {sort(nums.begin(),nums.end());int sum=0;for(int i=0;i<nums.size()-1;i+=2){sum+=min(nums[i],nums[i+1]);}return sum;}
};

時(shí)間復(fù)雜度：O(nlogn)即對(duì)數(shù)組nuts進(jìn)行排序的時(shí)間復(fù)雜度

空間復(fù)雜度：O(logn) 排序所需要使用的棧空間

4. 455 分發(fā)餅干

解法：雙指針+貪心

為了盡可能滿足最多數(shù)量的孩子，從貪心的角度考慮，應(yīng)該按照孩子的胃口從小到大的順序依次滿足每個(gè)孩子，且對(duì)于每個(gè)孩子，應(yīng)該選擇可以滿足這個(gè)孩子的胃口且尺寸最小的餅干。證明如下。

假設(shè)有 m 個(gè)孩子，胃口值分別是 $g_1$到 $g_m$，有 n塊餅干，尺寸分別是 $s_1$到 $s_n$，滿足 $g_i\le g_{i+1}$和 $s_j\le s_{j+1}$ ，其中 $1\le i<m$，$1\le j<n$。

假設(shè)在對(duì)前 i?1 個(gè)孩子分配餅干之后，可以滿足第 i 個(gè)孩子的胃口的最小的餅干是第 j 塊餅干，即 $s_j$是剩下的餅干中滿足 $g_i\le s_j$的最小值，最優(yōu)解是將第 j塊餅干分配給第 i個(gè)孩子。如果不這樣分配，考慮如下兩種情形：

如果 i<m 且 $g_{i+1}\le s_j$也成立，則如果將第 j 塊餅干分配給第 i+1個(gè)孩子，且還有剩余的餅干，則可以將第 j+1 塊餅干分配給第 iii 個(gè)孩子，分配的結(jié)果不會(huì)讓更多的孩子被滿足；

如果 j<n，則如果將第 j+1 塊餅干分配給第 i個(gè)孩子，當(dāng) $g_{i+1}\le s_j$時(shí)，可以將第 j塊餅干分配給第 i+1 個(gè)孩子，分配的結(jié)果不會(huì)讓更多的孩子被滿足；當(dāng) $g_{i+1}>s_j$時(shí)，第 j 塊餅干無(wú)法分配給任何孩子，因此剩下的可用的餅干少了一塊，因此分配的結(jié)果不會(huì)讓更多的孩子被滿足，甚至可能因?yàn)樯倭艘粔K可用的餅干而導(dǎo)致更少的孩子被滿足。

基于上述分析，可以使用貪心的方法盡可能滿足最多數(shù)量的孩子。

首先對(duì)數(shù)組 g 和 s 排序，然后從小到大遍歷 g 中的每個(gè)元素，對(duì)于每個(gè)元素找到能滿足該元素的 s 中的最小的元素。具體而言，令 i 是 g 的下標(biāo)，j是 s的下標(biāo)，初始時(shí) i 和 j 都為 0，進(jìn)行如下操作。

對(duì)于每個(gè)元素 g[i]，找到未被使用的最小的 j使得 $g[i]\le s[j]$，則 s[j] 可以滿足 g[i]。由于 g 和 s 已經(jīng)排好序，因此整個(gè)過(guò)程只需要對(duì)數(shù)組 g 和 s 各遍歷一次。當(dāng)兩個(gè)數(shù)組之一遍歷結(jié)束時(shí)，說(shuō)明所有的孩子都被分配到了餅干，或者所有的餅干都已經(jīng)被分配或被嘗試分配（可能有些餅干無(wú)法分配給任何孩子），此時(shí)被分配到餅干的孩子數(shù)量即為可以滿足的最多數(shù)量。

代碼：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int count=0;int sizeG=g.size();int sizeS=s.size();sort(g.begin(),g.end());sort(s.begin(),s.end());int i=0;int j=0;while(i<sizeG&&j<sizeS){if(g[i]>s[j]){j++;}else{i++;j++;count++;}}return count;}
};

時(shí)間復(fù)雜度：O(mlog?m+nlog?n)，其中 m 和 n 分別是數(shù)組 g 和 s 的長(zhǎng)度。對(duì)兩個(gè)數(shù)組排序的時(shí)間復(fù)雜度是 O(mlog?m+nlog?n)，遍歷數(shù)組的時(shí)間復(fù)雜度是 O(m+n)O(m+n)O(m+n)，因此總時(shí)間復(fù)雜度是 O(mlog?m+nlog?n)。

空間復(fù)雜度：O(log?m+log?n)，其中 m 和 n 分別是數(shù)組 g和 s的長(zhǎng)度?？臻g復(fù)雜度主要是排序的額外空間開(kāi)銷(xiāo)。

5. 575 分糖果

解法：貪心

設(shè)糖果的數(shù)量為n，因?yàn)樽疃嘀荒芊值揭话氲奶枪?#xff0c;答案不會(huì)超過(guò)$\frac{n}{2}$;設(shè)置糖果的種類(lèi)個(gè)數(shù)為numCandyType，答案也不會(huì)超過(guò)numCandyType。

利用set對(duì)candyType進(jìn)行去重，得到numCandyType的糖果種類(lèi)個(gè)數(shù)；

很顯然，如果$\frac{n}{2}>numType$；最多只能吃numType種類(lèi)的糖果；否則$\frac{n}{2}\le numType$，則最多也只能吃到 numType種的糖果

注意使用unordered_set的性能在此時(shí)大于set

1. 底層數(shù)據(jù)結(jié)構(gòu)：
   • std::set 是基于平衡二叉搜索樹(shù)（通常是紅黑樹(shù)）實(shí)現(xiàn)的，它保持元素有序，因此插入、刪除和查找的時(shí)間復(fù)雜度都是 O(log n)。
   • std::unordered_set 是基于哈希表實(shí)現(xiàn)的，它使用哈希函數(shù)將元素映射到桶中，插入、刪除和查找的平均時(shí)間復(fù)雜度是 O(1)。
2. 性能比較：
   • 在大多數(shù)情況下，std::unordered_set 的操作更快，因?yàn)楣１硗ǔＤ軌蛱峁└斓牟檎液筒迦氩僮鳌?/li>
   • 然而，在某些特定情況下（例如數(shù)據(jù)量較小或有序插入），std::set 的性能可能更好，因?yàn)樗恍枰幚砉_突，而且紅黑樹(shù)的有序性可能在某些操作上產(chǎn)生優(yōu)勢(shì)。
3. 迭代順序：
   • std::set 保持元素有序，因此在迭代時(shí)，元素以升序順序出現(xiàn)。
   • std::unordered_set 不保持元素的順序，迭代時(shí)元素的順序是不確定的。
4. 選擇適當(dāng)容器：
   • 選擇使用哪種容器應(yīng)取決于你的使用場(chǎng)景和需求。如果你需要有序性，并且能夠接受較慢的插入和查找，可以選擇 std::set。如果你更關(guān)注插入和查找的性能，并且不需要有序性，可以選擇 std::unordered_set。

代碼：

class Solution {
public:int distributeCandies(vector<int>& candyType) {std::set<int>CandyTypeSet(candyType.begin(),candyType.end());int numCandyType=CandyTypeSet.size();int n=candyType.size();if(n/2>numCandyType){return numCandyType;}return n/2;}
};

時(shí)間復(fù)雜度：O(n)，其中 n 是數(shù)組 CandyTypeSet 的長(zhǎng)度。

空間復(fù)雜度：O(n)。CandyTypeSet的哈希表需要O(n) 的空間。

6. 135 分發(fā)糖果

解法一：貪心算法

規(guī)則定義： 設(shè)學(xué)生 A 和學(xué)生 B 左右相鄰，A在 B 左邊；
左規(guī)則： 當(dāng) ratings[B]>ratings[A]時(shí)候，B 的糖比 A 的糖數(shù)量多。
右規(guī)則： 當(dāng) ratings[A]>ratings[B]時(shí)，A 的糖比 B 的糖數(shù)量多。
相鄰的學(xué)生中，評(píng)分高的學(xué)生必須獲得更多的糖果 等價(jià)于 所有學(xué)生滿足左規(guī)則且滿足右規(guī)則。

根據(jù)以上規(guī)則，我們可以從左向右按照左規(guī)則遍歷一遍，再?gòu)挠蚁蜃蟀凑沼乙?guī)則遍歷一遍；之后每次都取位置i的糖果最大數(shù)目，可以保證即滿足左規(guī)則又滿足了右邊規(guī)則；

算法流程：

先從左至右遍歷學(xué)生成績(jī) ratings，按照以下規(guī)則給糖，并記錄在 left 中，先給所有學(xué)生 1顆糖；

若 ratings[i]>ratings[i?1]，則第 i名學(xué)生糖比第 i?1 名學(xué)生多 1 個(gè)。

若 ratings[i]<=ratings[i?1] ，則第 i名學(xué)生糖數(shù)量不變。（交由從右向左遍歷時(shí)處理。）

經(jīng)過(guò)此規(guī)則分配后，可以保證所有學(xué)生糖數(shù)量 滿足左規(guī)則 。
同理，在此規(guī)則下從右至左遍歷學(xué)生成績(jī)并記錄在 right 中，可以保證所有學(xué)生糖數(shù)量 滿足右規(guī)則 。

最終，取以上 2輪遍歷 left 和 right 對(duì)應(yīng)學(xué)生糖果數(shù)的最大值 ，這樣則 同時(shí)滿足左規(guī)則和右規(guī)則 ，即得到每個(gè)同學(xué)的最少糖果數(shù)量。

【此過(guò)程可以在從右往左遍歷右規(guī)則時(shí)完成】

代碼：

class Solution {
public:int candy(vector<int>& ratings) {int n=ratings.size();int left[n];std::fill(left,left+n,1);int right[n];std::fill(right,right+n,1);for(int i=1;i<n;i++){if(ratings[i]>ratings[i-1]){left[i]=left[i-1]+1;}}int count=left[n-1];for(int i=n-2;i>=0;i--){if(ratings[i]>ratings[i+1]){
#從右邊往左時(shí)候，遞歸記錄的是最后一個(gè)位置的糖果個(gè)數(shù)，一直遞歸影響到前面位置的糖果個(gè)數(shù)              right[i]=right[i+1]+1;}count+=max(left[i],right[i]);}return count;}
};

時(shí)間復(fù)雜度：O(n)，其中 n 是孩子的數(shù)量。我們需要遍歷兩次數(shù)組以分別計(jì)算滿足左規(guī)則或右規(guī)則的最少糖果數(shù)量。

空間復(fù)雜度：O(n)，其中 n 是孩子的數(shù)量。我們需要保存所有的左規(guī)則對(duì)應(yīng)的糖果數(shù)量。

解法二：常數(shù)空間遍歷

參考力扣官方題解：135. 分發(fā)糖果 - 力扣（LeetCode）

注意到糖果總是盡量少給，且從 11開(kāi)始累計(jì)，每次要么比相鄰的同學(xué)多給一個(gè)，要么重新置為 1。依據(jù)此規(guī)則，我們可以畫(huà)出下圖：

• 上述為例子[1,3,5,2,3,3]的最后的解

• 其中相同顏色的柱狀圖的高度總恰好為 1,2,3…。

  而高度也不一定一定是升序，也可能是 …3,2,1的降序：

  

• 上述為數(shù)組[1,3,5,3,2,2]的解

• 注意到在上圖中，對(duì)于第三個(gè)同學(xué)，他既可以被認(rèn)為是屬于綠色的升序部分，也可以被認(rèn)為是屬于藍(lán)色的降序部分。因?yàn)樗瑫r(shí)比兩邊的同學(xué)評(píng)分更高。我們對(duì)序列稍作修改：

  

?

• 注意到右邊的升序部分變長(zhǎng)了，使得第三個(gè)同學(xué)不得不被分配 4個(gè)糖果。
• 依據(jù)前面總結(jié)的規(guī)律，我們可以提出本題的解法。我們從左到右枚舉每一個(gè)同學(xué)，記前一個(gè)同學(xué)分得的糖果數(shù)量為 pre：
• 如果當(dāng)前同學(xué)比上一個(gè)同學(xué)評(píng)分高，說(shuō)明我們就在最近的遞增序列中，直接分配給該同學(xué) pre+1 個(gè)糖果即可。
• 否則我們就在一個(gè)遞減序列中，我們直接分配給當(dāng)前同學(xué)一個(gè)糖果，并把該同學(xué)所在的遞減序列中所有的同學(xué)都再多分配一個(gè)糖果，以保證糖果數(shù)量還是滿足條件。
• 我們無(wú)需顯式地額外分配糖果，只需要記錄當(dāng)前的遞減序列長(zhǎng)度，即可知道需要額外分配的糖果數(shù)量。
• 同時(shí)注意當(dāng)當(dāng)前的遞減序列長(zhǎng)度和上一個(gè)遞增序列等長(zhǎng)時(shí)，需要把最近的遞增序列的最后一個(gè)同學(xué)也并進(jìn)遞減序列中。
• 這樣，我們只要記錄當(dāng)前遞減序列的長(zhǎng)度 dec，最近的遞增序列的長(zhǎng)度 inc 和前一個(gè)同學(xué)分得的糖果數(shù)量 pre 即可。

代碼：

class Solution {
public:int candy(vector<int>& ratings) {int n=ratings.size();int ret=1;int inc=1,dec=0,pre=1;for(int i=1;i<n;i++){if(ratings[i]>=ratings[i-1]){//將遞減序列的個(gè)數(shù)清0dec=0;pre=ratings[i]==ratings[i-1]?1:pre+1;ret+=pre;inc=pre;}else{//遞減序列，記錄遞減序列的值dec++;//標(biāo)志位置相同，如123321，此時(shí)遞增序列的末尾3必須加1，合并到遞減序列中if(dec==inc){dec++;}ret+=dec;//pre還原為初始值1，為了后續(xù)遞增準(zhǔn)備pre=1;}}return ret;}
};

時(shí)間復(fù)雜度：O(n)，其中 n 是孩子的數(shù)量。我們需要遍歷兩次數(shù)組以分別計(jì)算滿足左規(guī)則或右規(guī)則的最少糖果數(shù)量。

空間復(fù)雜度：O(1)。我們只需要常數(shù)的空間保存若干變量。

7. 409 最長(zhǎng)回文串

解法：貪心算法

回文串是一個(gè)正著讀和反著讀都一樣的字符串。以回文中心為分界線，對(duì)于回文串中左側(cè)的字符 ch，在右側(cè)對(duì)稱的位置也會(huì)出現(xiàn)同樣的字符。例如在字符串 “abba” 中，回文中心是 “ab|ba” 中豎線的位置，而在字符串 “abcba” 中，回文中心是 “ab?ba” 中的字符 “c” 本身。我們可以發(fā)現(xiàn)，在一個(gè)回文串中，只有最多一個(gè)字符出現(xiàn)了奇數(shù)次，其余的字符都出現(xiàn)偶數(shù)次。

我們可以將每個(gè)字符使用偶數(shù)次，使得它們根據(jù)回文中心對(duì)稱。在這之后，如果有剩余的字符，我們可以再取出一個(gè)，作為回文中心。

算法

• 首先利用letterToCount統(tǒng)計(jì)字符串中每個(gè)字符出現(xiàn)的個(gè)數(shù)，設(shè)置結(jié)果為result,然后遍歷letterToCount的value
• 如果value是偶數(shù)，則直接與result相加；如果value是奇數(shù)，則將value-1與result相加，并且flag設(shè)置為1
• 最后若flag為1，就說(shuō)明字符中有單個(gè)的字符存在，可以作為回文串中的中心點(diǎn)，因此將result++;

class Solution {
public:int longestPalindrome(string s) {unordered_map<char,int>letterToCount;for(auto letter:s){letterToCount[letter]++;}int result=0;int flag=0;for(auto it=letterToCount.begin();it!=letterToCount.end();it++){if(it->second%2==0){result+=it->second;}else{result+=(it->second-1);flag=1;}}if(flag)result++;return result;}
};

時(shí)間復(fù)雜度：O(N)，其中 N 為字符串 s 的長(zhǎng)度。我們需要遍歷每個(gè)字符一次。

空間復(fù)雜度：O(S)，其中 S 為字符集大小，在c++中使用哈希映射，最多只會(huì)存儲(chǔ) 52 個(gè)（即小寫(xiě)字母與大寫(xiě)字母的數(shù)量之和）鍵值對(duì)。

8. 621 任務(wù)調(diào)度器

解法：桶思想

• 先考慮最為簡(jiǎn)單的情況：假設(shè)只有一類(lèi)任務(wù)，除了最后一個(gè)任務(wù)以外，其余任務(wù)在安排后均需要增加 n 個(gè)單位的凍結(jié)時(shí)間。設(shè)這類(lèi)任務(wù)的個(gè)數(shù)為max，則需要構(gòu)造max個(gè)桶，每個(gè)桶最多保存n+1個(gè)任務(wù)。

  

• 將任務(wù)數(shù)記為 m 個(gè)，其中前m?1 個(gè)任務(wù)均要消耗n+1 的單位時(shí)間，最后一個(gè)任務(wù)僅消耗 1 個(gè)單位時(shí)間，即所需要的時(shí)間為 (n+1)×(m?1)+1。

• 當(dāng)存在多個(gè)任務(wù)時(shí)，由于每一類(lèi)任務(wù)都需要被完成，因此本質(zhì)上我們最需要考慮的是將數(shù)量最大的任務(wù)安排掉，其他任務(wù)則是間插其中。

  假設(shè)數(shù)量最大的任務(wù)數(shù)為 max，共有 tot 個(gè)任務(wù)數(shù)為 max 的任務(wù)種類(lèi)。

  實(shí)際上，當(dāng)任務(wù)總數(shù)不超過(guò) (n+1)×(max??1)+tot （注意tot就是最后一行的任務(wù)數(shù)）時(shí)，我們總能將其他任務(wù)插到空閑時(shí)間中去，不會(huì)引入額外的凍結(jié)時(shí)間（下左圖）；而當(dāng)任務(wù)數(shù)超過(guò)該值時(shí)，我們可以在將其橫向添加每個(gè) n+1 塊的后面，同時(shí)不會(huì)引入額外的凍結(jié)時(shí)間（下右圖）：

  

  注意到，左圖中的任務(wù)所需的最短時(shí)間其實(shí)為 (n+1)×(max??1)+tot ，而右圖中的最短時(shí)間就是其task序列的長(zhǎng)度本身，若是超過(guò)了(n+1)×(max??1)+tot ，那么其所需的時(shí)間就是task的長(zhǎng)度。

  因此，我們需要返回的就是二者之中的最大值即可

? 代碼：

class Solution {
public:int leastInterval(vector<char>& tasks, int n) {if(n==0)return tasks.size();vector<int>letterToCount(26);for(char c:tasks){letterToCount[c-'A']++;}int maxCnt=0,tot=0;for(int i=0;i<letterToCount.size();i++){maxCnt=std::max(maxCnt,letterToCount[i]);}for(int i=0;i<letterToCount.size();i++){if(letterToCount[i]==maxCnt)tot++;}int len=tasks.size();return std::max((n+1)*(maxCnt-1)+tot,len);}
};

• 時(shí)間復(fù)雜度：O*(n+*C)
• 空間復(fù)雜度：O?，其中 C=26 為任務(wù)字符集大小

9. 179 最大數(shù)

解法：貪心+自定義排序

對(duì)于 nums中的任意兩個(gè)值 a 和 b，我們無(wú)法直接從常規(guī)角度上確定其大小/先后關(guān)系。

但我們可以根據(jù)「結(jié)果」來(lái)決定 a和 b 的排序關(guān)系：

如果拼接結(jié)果 ab 要比 ba好，那么我們會(huì)認(rèn)為 a應(yīng)該放在 b 前面。

例如上面的示例2中，30和3的大小比較，我們認(rèn)為"3>30",原因是：330>303，即ab的拼接結(jié)果比ba好。

算法流程：

• 首先設(shè)置數(shù)組str，將nums數(shù)組轉(zhuǎn)為字符串

• 然后使用自定義排序，定義排序規(guī)則為拼接后的字符串的大小比較

• 最后將數(shù)組str中的字符串轉(zhuǎn)為輸出的字符串

  另外，注意我們需要處理前導(dǎo)零（最多保留一位）。即如果最后的答案的第一位是‘0’，就直接返回’0’

貪心算法的解法的正確性證明可見(jiàn)：179. 最大數(shù) - 力扣（LeetCode）

代碼：

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string>str;for(int i:nums){str.emplace_back(to_string(i));}sort(str.begin(),str.end(),[](const string left,const string right){return left+right>right+left;});string result="";for(auto c:str){result+=c;}if(result[0]=='0'){return "0";}return result;}
};

時(shí)間復(fù)雜度：O（n logn)

空間復(fù)雜度：O(logn)

10. 56 合并區(qū)間

解法：排序+貪心

用數(shù)組res存儲(chǔ)最終的答案。

首先，我們將列表中的區(qū)間按照左端點(diǎn)升序排序。然后我們將第一個(gè)區(qū)間加入 res 數(shù)組中，并按順序依次考慮之后的每個(gè)區(qū)間：

如果當(dāng)前區(qū)間的左端點(diǎn)在數(shù)組res 中最后一個(gè)區(qū)間的右端點(diǎn)之后，那么它們不會(huì)重合，我們可以直接將這個(gè)區(qū)間加入數(shù)組 merged 的末尾；

否則，它們重合，我們需要用當(dāng)前區(qū)間的右端點(diǎn)更新數(shù)組 merged 中最后一個(gè)區(qū)間的右端點(diǎn)，將其置為二者的較大值。

其正確性可見(jiàn)官方題解：

56. 合并區(qū)間 - 力扣（LeetCode）

代碼：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>>res;if(intervals.size()==1)return intervals;sort(intervals.begin(),intervals.end());res.push_back(intervals[0]);for(int i=1;i<intervals.size();i++){int left=res.back()[0];int right=res.back()[1];if(intervals[i][0]<=right){if(intervals[i][1]>right){res.pop_back();res.push_back({left,intervals[i][1]});}   }else{res.push_back(intervals[i]);}}return res;}
};

時(shí)間復(fù)雜度：O(nlogn)，其中 n 為區(qū)間的數(shù)量。除去排序的開(kāi)銷(xiāo)，我們只需要一次線性掃描，所以主要的時(shí)間開(kāi)銷(xiāo)是排序的O(nlogn)。

空間復(fù)雜度：O(logn)，其中 n 為區(qū)間的數(shù)量。這里計(jì)算的是存儲(chǔ)答案之外，使用的額外空間。O(logn) 即為排序所需要的空間復(fù)雜度。

11. 57 插入?yún)^(qū)間

解法：模擬+區(qū)間合并+一次遍歷

• 對(duì)于區(qū)間 $S1=[l_1,r_1] $和 $S_2=[l_2,r_2]$S，如果它們之間沒(méi)有重疊（沒(méi)有交集），說(shuō)明要么 $S_1$在 $S_2$的左側(cè)，此時(shí)有 $r_1<l_2$；要么 $S_1$在 $S_2$的右側(cè)，此時(shí)有 $l_1>r_2$。

• 如果 $r_1<l_2$和 $l_1>r_2$二者均不滿足，說(shuō)明 $S_1$ 和 $S_2$ 必定有交集，它們的交集即為$[\max (l_1,l_2),\min (r_1,r_2)]$,并集為$[\min (l_1,l_2),\max (r_1,r_2)]$

算法思路：

• 在給定的區(qū)間集合 $\mathcal{X}$ 互不重疊的前提下，當(dāng)我們需要插入一個(gè)新的區(qū)間 $S=[\text{left},\text{right}]$時(shí)，我們只需要：
• 找出所有與區(qū)間 S 重疊的區(qū)間集合 ${\mathcal{X}}^{\prime }$,將 ${\mathcal{X}}^{\prime }$ 中的所有區(qū)間連帶上區(qū)間 S 合并成一個(gè)大區(qū)間；
  最終的答案即為不與${\mathcal{X}}^{\prime }$ 重疊的區(qū)間以及合并后的大區(qū)間。

這樣做的正確性在于，給定的區(qū)間集合中任意兩個(gè)區(qū)間都是沒(méi)有交集的，因此所有需要合并的區(qū)間，就是所有與區(qū)間 S 重疊的區(qū)間。

并且，在給定的區(qū)間集合已經(jīng)按照左端點(diǎn)排序的前提下，所有與區(qū)間 S 重疊的區(qū)間在數(shù)組$\text{intervals}$ 中下標(biāo)范圍是連續(xù)的，因此我們可以對(duì)所有的區(qū)間進(jìn)行一次遍歷，就可以找到這個(gè)連續(xù)的下標(biāo)范圍。

當(dāng)我們遍歷到區(qū)間 $[l_i,r_i]$時(shí)：

如果 $r_i<\text{left}$，說(shuō)明 $[l_i,r_i]$ 與 S 不重疊并且在其左側(cè)，我們可以直接將$[l_i,r_i]$加入答案；

如果$l_i>\text{right}$，說(shuō)明$[l_i,r_i]$與 S 不重疊并且在其右側(cè)，我們可以直接將$[l_i,r_i]$加入答案；

如果上面兩種情況均不滿足，說(shuō)明 $[l_i,r_i]$與 S 重疊，我們無(wú)需將 $[l_i,r_i]$ 加入答案。此時(shí)，我們需要將 S 與 $[l_i,r_i]$
合并，即將 S 更新為其與$[l_i,r_i]$的并集。

那么我們應(yīng)當(dāng)在什么時(shí)候?qū)^(qū)間 S 加入答案呢？由于我們需要保證答案也是按照左端點(diǎn)排序的，因此當(dāng)我們遇到第一個(gè) 滿足 $l_i>\text{right}$

的區(qū)間時(shí)，說(shuō)明以后遍歷到的區(qū)間不會(huì)與 S 重疊，并且它們左端點(diǎn)一定會(huì)大于 S 的左端點(diǎn)。此時(shí)我們就可以將 S 加入答案。特別地，如果不存在這樣的區(qū)間，我們需要在遍歷結(jié)束后，將 S 加入答案。

代碼：

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>>res;int n=intervals.size();bool isInsert=false;int left=newInterval[0];int right=newInterval[1];for(int i=0;i<n;i++){if(intervals[i][1]<left){res.push_back(intervals[i]);}else if(intervals[i][0]>right){if(!isInsert){//找到了插入位置res.push_back({left,right});isInsert=true;}res.push_back(intervals[i]);}else{//有交集left=min(left,intervals[i][0]);right=max(right,intervals[i][1]);}}if(!isInsert){res.push_back({left,right});}return res;}
};

時(shí)間復(fù)雜度：O(n)，其中 n 是數(shù)組 intervals 的長(zhǎng)度，即給定的區(qū)間個(gè)數(shù)。

空間復(fù)雜度：O(1)。除了存儲(chǔ)返回答案的空間以外，我們只需要額外的常數(shù)空間即可。

13. 452 用最少數(shù)量的箭引爆氣球

解法：排序+貪心

我們把氣球看做區(qū)間，箭還是箭，箭是垂直向上射出。

首先，對(duì)于右端點(diǎn)最小的那個(gè)區(qū)間，如果想要用箭穿過(guò)它，那么一定從它的右端點(diǎn)穿過(guò)（從右端點(diǎn)穿過(guò)才只會(huì)穿過(guò)更多的區(qū)間）。
接下來(lái)，對(duì)于這只箭能未能穿過(guò)的區(qū)間，再?gòu)闹姓页鲇叶它c(diǎn)最小的區(qū)間。對(duì)于這只箭未能穿過(guò)的區(qū)間，如此往復(fù)的找下去。最終我們使用的箭數(shù)就是最少的。

如何尋找第一個(gè)右端點(diǎn)最小的區(qū)間，以及在未被第一支箭穿過(guò)的剩余區(qū)間中，繼續(xù)尋找第一個(gè)右端點(diǎn)最小的區(qū)間呢？

當(dāng)我們把每個(gè)區(qū)間按照右端點(diǎn)升序排序后，顯然第一個(gè)區(qū)間就是我們最開(kāi)始要找的第一個(gè)區(qū)間，后序也可以進(jìn)一步找到滿足條件的最小右端點(diǎn)區(qū)間。具體的過(guò)程如下：

首先將區(qū)間按照右端點(diǎn)升序排序，此時(shí)位序?yàn)?的區(qū)間就是我們要找的第一個(gè)區(qū)間（如圖），我們需要記錄下第一個(gè)區(qū)間的右端點(diǎn)right（射出第一支箭），然后繼續(xù)遍歷，此時(shí)就會(huì)存在兩種情況：

對(duì)于左端點(diǎn)小于等于right的區(qū)間，說(shuō)明該區(qū)間能被前面的箭（right）穿過(guò)。
對(duì)于接下來(lái)左端點(diǎn)大于right的區(qū)間，說(shuō)明前面這支箭無(wú)法穿過(guò)該區(qū)間（即：該區(qū)間就是未被箭穿過(guò)的區(qū)間集合的第一個(gè)區(qū)間），我們又找到了第一個(gè)未被箭穿過(guò)的區(qū)間，此時(shí)我們用一把新的箭穿過(guò)該區(qū)間的右端點(diǎn)（即更新right = points[i][1]），并將使用的箭數(shù)+1。如此往復(fù)。

代碼：

bool pointscmp(const vector<int>&a,const vector<int>&b){return a[1]<b[1];
}
class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(),points.end(),pointscmp);int result=1;int arrow=points[0][1];int n=points.size();for(int i=1;i<n;i++){if(points[i][0]<=arrow){continue;}arrow=points[i][1];result++;}return result;}
};

時(shí)間復(fù)雜度：O(nlog?n)，其中 nn是數(shù)組 points 的長(zhǎng)度。排序的時(shí)間復(fù)雜度為 O(nlog?n)，對(duì)所有氣球進(jìn)行遍歷并計(jì)算答案的時(shí)間復(fù)雜度為 O(n)，其在漸進(jìn)意義下小于前者，因此可以忽略。

空間復(fù)雜度：O(logn)，即為排序需要使用的?？臻g。

14. 435 無(wú)重疊區(qū)間

解法一：排序+貪心

關(guān)于為什么是按照區(qū)間右端點(diǎn)排序？
官解里對(duì)這個(gè)描述的非常清楚了，這個(gè)題其實(shí)是預(yù)定會(huì)議的一個(gè)問(wèn)題，給你若干時(shí)間的會(huì)議，然后去預(yù)定會(huì)議，那么能夠預(yù)定的最大的會(huì)議數(shù)量是多少？核心在于我們要找到最大不重疊區(qū)間的個(gè)數(shù)。 如果我們把本題的區(qū)間看成是會(huì)議，那么按照右端點(diǎn)排序，我們一定能夠找到一個(gè)最先結(jié)束的會(huì)議，而這個(gè)會(huì)議一定是我們需要添加到最終結(jié)果的的首個(gè)會(huì)議。（這個(gè)不難貪心得到，因?yàn)檫@樣能夠給后面預(yù)留的時(shí)間更長(zhǎng)）。

關(guān)于為什么是不能按照區(qū)間左端點(diǎn)排序？
這里補(bǔ)充一下為什么不能按照區(qū)間左端點(diǎn)排序。同樣地，我們把本題的區(qū)間看成是會(huì)議，如果“按照左端點(diǎn)排序，我們一定能夠找到一個(gè)最先開(kāi)始的會(huì)議”，但是最先開(kāi)始的會(huì)議，不一定最先結(jié)束。。舉個(gè)例子：

區(qū)間a是最先開(kāi)始的，如果我們采用區(qū)間a作為放入最大不重疊區(qū)間的首個(gè)區(qū)間，那么后面我們只能采用區(qū)間d作為第二個(gè)放入最大不重疊區(qū)間的區(qū)間，但這樣的話，最大不重疊區(qū)間的數(shù)量為2。但是如果我們采用區(qū)間b作為放入最大不重疊區(qū)間的首個(gè)區(qū)間，那么最大不重疊區(qū)間的數(shù)量為3，因?yàn)閰^(qū)間b是最先結(jié)束的。

代碼：

class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {if(intervals.size()==1||intervals.size()==0)return 0;sort(intervals.begin(),intervals.end(),[](const auto &u,const auto &v){return u[1]<v[1];});int n=intervals.size();int right=intervals[0][1];int ans=1;for(int i=1;i<n;i++){if(intervals[i][0]>=right){ans++;right=intervals[i][1];}}return n-ans;}
};

時(shí)間復(fù)雜度：O(nlogn)，其中 n 是區(qū)間的數(shù)量。我們需要 O(nlog?n) 的時(shí)間對(duì)所有的區(qū)間按照右端點(diǎn)進(jìn)行升序排序，并且需要O(n) 的時(shí)間進(jìn)行遍歷。由于前者在漸進(jìn)意義下大于后者，因此總時(shí)間復(fù)雜度為O(nlogn)。

空間復(fù)雜度：O(logn)，即為排序需要使用的?？臻g。

解法二：動(dòng)態(tài)規(guī)劃

見(jiàn)官方題解，此解法的時(shí)間復(fù)雜度過(guò)高，會(huì)超出時(shí)間限制

435. 無(wú)重疊區(qū)間 - 力扣（LeetCode）

15. 646 最長(zhǎng)數(shù)對(duì)鏈

解法一：排序+貪心

這題解法和435無(wú)重疊區(qū)間基本相同，僅僅是判斷條件不同，無(wú)重疊子區(qū)間要求邊界點(diǎn)可以重疊，如[1,2]和[2,3]；但是646要求邊界點(diǎn)不重疊；

代碼：

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {if(pairs.size()==1)return 1;sort(pairs.begin(),pairs.end(),[](const auto &u,const auto &v){return u[1]<v[1];});int n=pairs.size();int ans=1;int right=0;for(int i=1;i<n;i++){if(pairs[i][0]>pairs[right][1]){ans++;right=i;}}return ans;}
};

時(shí)間復(fù)雜度：O(nlog?n)，其中 n 為 pairs 的長(zhǎng)度。排序的時(shí)間復(fù)雜度為 O(nlog?n)。

空間復(fù)雜度：O(log?n)，為排序的空間復(fù)雜度。

解法二：動(dòng)態(tài)規(guī)劃

定義 dp[i] 為以 pairs[i] 為結(jié)尾的最長(zhǎng)數(shù)對(duì)鏈的長(zhǎng)度。計(jì)算 dp[i] 時(shí)，可以先找出所有的滿足 $\text{pairs}[i][0]>\text{pairs}[j][1]$的 j，并求出最大的 dp[j]的值即可賦為這個(gè)最大值加一。這種動(dòng)態(tài)規(guī)劃的思路要求計(jì)算dp[i] 時(shí)，所有潛在的 dp[j] 已經(jīng)計(jì)算完成，可以先將 pairs 進(jìn)行排序來(lái)滿足這一要求。初始化時(shí)，dp 需要全部賦值為 1。

代碼：

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {int n=pairs.size();vector<int>dp(n,1);sort(pairs.begin(),pairs.end());for(int i=0;i<n;i++)for(int j=0;j<i;j++){if(pairs[i][0]>pairs[j][1]){dp[i]=max(dp[i],dp[j]+1);}}return dp[n-1];}
};

時(shí)間復(fù)雜度：O(n^2)，其中 n 為 pairs 的長(zhǎng)度。排序的時(shí)間復(fù)雜度為 O(nlogn)，兩層 for 循環(huán)的時(shí)間復(fù)雜度為 O(n^2)

空間復(fù)雜度：O(n)，數(shù)組 dp 的空間復(fù)雜度為 O(n)。

解法三：最長(zhǎng)上升子序列

解法二實(shí)際上是最長(zhǎng)遞增子序列的動(dòng)態(tài)規(guī)劃解法，這個(gè)解法可以改造為貪心 + 二分查找的形式。用一個(gè)數(shù)組arr 來(lái)記錄當(dāng)前最優(yōu)情況，arr[i]就表示長(zhǎng)度為 i+1i 的數(shù)對(duì)鏈的末尾可以取得的最小值，遇到一個(gè)新數(shù)對(duì)時(shí)，先用二分查找得到這個(gè)數(shù)對(duì)可以放置的位置，再更新 arr。

注意：由于是最長(zhǎng)上升子序列，如果新數(shù)(left)大于arr末尾的值(right)，則直接加入；否則就在arr中找到left所在的位置，判斷此時(shí)對(duì)應(yīng)的right和arr中記錄的right哪個(gè)更小，取更小的值

代碼：

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(),pairs.end());vector<int>arr;for(auto p:pairs){int left=p[0];int right=p[1];if(arr.empty()||left>arr.back())arr.push_back(right);else{int idx=lower_bound(arr.begin(),arr.end(),left)-arr.begin();arr[idx]=min(arr[idx],right);}}return arr.size();}
};

時(shí)間復(fù)雜度：O(nlog?n)，其中 n 為 pairs 的長(zhǎng)度。排序的時(shí)間復(fù)雜度為 O(nlog?n)，二分查找的時(shí)間復(fù)雜度為 O(nlog?n)，二分的次數(shù)為 O(n)。

空間復(fù)雜度：O(n)，數(shù)組 arr 的長(zhǎng)度最多為 O(n)。

16. 406 按照身高重建隊(duì)列

解法：排序+貪心

題目描述：整數(shù)對(duì) (h, k) 表示，其中 h 是這個(gè)人的身高，k 是排在這個(gè)人前面且身高大于或等于 h 的人數(shù)。

一般這種數(shù)對(duì)，還涉及排序的，根據(jù)第一個(gè)元素正向排序，根據(jù)第二個(gè)元素反向排序，或者根據(jù)第一個(gè)元素反向排序，根據(jù)第二個(gè)元素正向排序，往往能夠簡(jiǎn)化解題過(guò)程。

在本題目中，我首先對(duì)數(shù)對(duì)進(jìn)行排序，按照數(shù)對(duì)的元素 1 降序排序，按照數(shù)對(duì)的元素 2 升序排序。

原因是，按照元素 1 進(jìn)行降序排序，對(duì)于每個(gè)元素，在其之前的元素的個(gè)數(shù)，就是大于等于他的元素的數(shù)量，而按照第二個(gè)元素正向排序，我們希望 k 大的盡量在后面，減少插入操作的次數(shù)。

算法步驟：

• 排序，按照元素1降序排序，元素2升序排序
• 創(chuàng)建空數(shù)組result表示結(jié)果
• 遍歷people[i]，若是元素2的值等于result的長(zhǎng)度，或者result為空，直接在尾部插入peple[i],否則則在元素2的位置插入people[i]

代碼：

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {vector<vector<int>>result;  sort(people.begin(),people.end(),[](const auto &u,const auto & v){if(u[0]!=v[0])return u[0]>v[0];elsereturn u[1]<v[1];});int n=people.size();for(int i=0;i<n;i++){int s=people[i][1];if(result.size()==people[i][1]||result.empty()){result.emplace_back(people[i]);}else{result.insert(result.begin()+s,people[i]);}}return result;}
};

時(shí)間復(fù)雜度：O(n^2)，其中 n 是數(shù)組 people 的長(zhǎng)度。我們需要 )O(nlogn) 的時(shí)間進(jìn)行排序，隨后需要 O(n^2) 的時(shí)間遍歷每一個(gè)人并將他們放入隊(duì)列中。由于前者在漸近意義下小于后者，因此總時(shí)間復(fù)雜度為 O(n^2)。

空間復(fù)雜度：O(log?n)。

17. 48 旋轉(zhuǎn)圖像

解法一：遞推公式，分組旋轉(zhuǎn)

首先我們由示例2可以觀察到如下圖所示，矩陣順時(shí)針旋轉(zhuǎn) 90o 后，可找到以下規(guī)律：

「第 i 行」元素旋轉(zhuǎn)到「第 n?1?i列」元素；
「第 j列」元素旋轉(zhuǎn)到「第 j 行」元素；

因此，對(duì)于矩陣任意第 i行、第 j 列元素 $matrix[i][j]$ ，矩陣旋轉(zhuǎn) 90o 后「元素位置旋轉(zhuǎn)公式」為：

$\begin{array}{rl}matrix[i][j]& \to matrix[j][n?1?i]\end{array}$

$\begin{array}{rl}原索引位置& \to 旋轉(zhuǎn)后索引位置\end{array}$

• 以位于矩陣四個(gè)角點(diǎn)的元素為例，設(shè)矩陣左上角元素 A 、右上角元素 B 、右下角元素 C 、左下角元素 D 。矩陣旋轉(zhuǎn) 90o 后，相當(dāng)于依次先后執(zhí)行 D→A , C→D , B→C, A→B修改元素，即如下「首尾相接」的元素旋轉(zhuǎn)操作：

如上圖所示，由于第 1 步 D→A 已經(jīng)將 A覆蓋（導(dǎo)致 A丟失），此丟失導(dǎo)致最后第 A→B 無(wú)法賦值。為解決此問(wèn)題，考慮借助一個(gè)「輔助變量 tmp預(yù)先存儲(chǔ) A ，此時(shí)的旋轉(zhuǎn)操作變?yōu)?#xff1a;

暫存 tmp=A
A←D←C←B←tmp

如上圖所示，一輪可以完成矩陣 4 個(gè)元素的旋轉(zhuǎn)。因而，只要分別以矩陣左上角 1/41/41/4 的各元素為起始點(diǎn)執(zhí)行以上旋轉(zhuǎn)操作，即可完整實(shí)現(xiàn)矩陣旋轉(zhuǎn)。

具體來(lái)看，當(dāng)矩陣大小 n 為偶數(shù)時(shí)，取前$\frac{n}{2}$ 行、前 $\frac{n}{2} $列的元素為起始點(diǎn)；當(dāng)矩陣大小 n 為奇數(shù)時(shí)，取前 $\frac{n}{2} $行、前 $\frac{n + 1}{2} $ 列的元素為起始點(diǎn)。

令 $matrix[i][j]=A$，根據(jù)文章開(kāi)頭的元素旋轉(zhuǎn)公式，可推導(dǎo)得適用于任意起始點(diǎn)的元素旋轉(zhuǎn)操作：

暫存

$tmp=matrix[i[j]$

$matrix[i[j]\leftarrow matrix[n?1?j][i]\leftarrow matrix[n?1?i][n?1?j]\leftarrow matrix[j][n?1?i]\leftarrow tmp$

代碼：

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n=matrix.size();for(int i=0;i<n/2;i++)for(int j=0;j<(n+1)/2;j++){int tmp=matrix[i][j];matrix[i][j]=matrix[n-1-j][i];matrix[n-1-j][i]=matrix[n-1-i][n-1-j];matrix[n-1-i][n-1-j]=matrix[j][n-1-i];matrix[j][n-1-i]=tmp;}}
};

時(shí)間復(fù)雜度 O(N^2) ： 其中 N 為輸入矩陣的行（列）數(shù)。需要將矩陣中每個(gè)元素旋轉(zhuǎn)到新的位置，即對(duì)矩陣所有元素操作一次，使用 O(N^2)時(shí)間。
空間復(fù)雜度 O(1) ： 臨時(shí)變量 tmp 使用常數(shù)大小的額外空間。值得注意，當(dāng)循環(huán)中進(jìn)入下輪迭代，上輪迭代初始化的 tmp 占用的內(nèi)存就會(huì)被自動(dòng)釋放，因此無(wú)累計(jì)使用空間。

解法二：用翻轉(zhuǎn)代替旋轉(zhuǎn)

見(jiàn)官方題解：48. 旋轉(zhuǎn)圖像 - 力扣（LeetCode）

代碼：

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n=matrix.size();//水平翻轉(zhuǎn)for(int i=0;i<n/2;i++){for(int j=0;j<n;j++){swap(matrix[i][j],matrix[n-1-i][j]);}}//主對(duì)角線翻轉(zhuǎn)for(int i=0;i<n;i++){for(int j=0;j<i;j++){swap(matrix[i][j],matrix[j][i]);}}}
};

時(shí)間復(fù)雜度：O(N^2)，其中 N 是 matrix 的邊長(zhǎng)。對(duì)于每一次翻轉(zhuǎn)操作，我們都需要枚舉矩陣中一半的元素。

空間復(fù)雜度：O(1)。為原地翻轉(zhuǎn)得到的原地旋轉(zhuǎn)。

18. 169 多數(shù)元素

解法一：哈希表

使用hash表存儲(chǔ)每個(gè)元素的數(shù)量，如果大于n/2，則返回，因?yàn)轭}目應(yīng)該多數(shù)元素之存在一個(gè)

代碼：

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int>numToSize;for(auto n:nums){numToSize[n]++;if(numToSize[n]>nums.size()/2){return n;}}return 0;}
};

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

解法二：Boyer-Moore 算法【實(shí)現(xiàn)O(1)的空間復(fù)雜度】

見(jiàn)官方題解

代碼：

class Solution {
public:int majorityElement(vector<int>& nums) {int candidate=-1;int count=0;for(int num:nums){if(num==candidate)count++;else if(--count<0){candidate=num;count=1;}}return candidate;}
};

時(shí)間復(fù)雜度:O(n)

空間復(fù)雜度:O(1)

解法：排序法、分治法、隨機(jī)化、可見(jiàn)官方題解

169. 多數(shù)元素 - 力扣（LeetCode）

19. 215 數(shù)組中的第k個(gè)最大元素

解法：改進(jìn)版的快排

我們可以用快速排序來(lái)解決這個(gè)問(wèn)題，先對(duì)原數(shù)組排序，再返回倒數(shù)第 kkk 個(gè)位置，這樣平均時(shí)間復(fù)雜度是 O(nlog?n)O(n \log n)O(nlogn)，但其實(shí)我們可以做的更快。

首先我們來(lái)回顧一下快速排序，這是一個(gè)典型的分治算法。我們對(duì)數(shù)組 a[l?r] 做快速排序的過(guò)程是（參考《算法導(dǎo)論》）：

分解： 將數(shù)組 a[l?r]「劃分」成兩個(gè)子數(shù)組 a[l?q?1]、a[q+1?r]，使得 a[l?q?1] 中的每個(gè)元素小于等于 a[q]，且 a[q] 小于等于 a[q+1?r] 中的每個(gè)元素。其中，計(jì)算下標(biāo) q 也是「劃分」過(guò)程的一部分。
解決： 通過(guò)遞歸調(diào)用快速排序，對(duì)子數(shù)組 a[l?q?1]和 a[q+1?r]進(jìn)行排序。
合并： 因?yàn)樽訑?shù)組都是原址排序的，所以不需要進(jìn)行合并操作，a[l?r]已經(jīng)有序。
上文中提到的 「劃分」 過(guò)程是：從子數(shù)組 a[l?r]中選擇任意一個(gè)元素 x作為主元，調(diào)整子數(shù)組的元素使得左邊的元素都小于等于它，右邊的元素都大于等于它， x 的最終位置就是 q。
由此可以發(fā)現(xiàn)每次經(jīng)過(guò)「劃分」操作后，我們一定可以確定一個(gè)元素的最終位置，即 x的最終位置為 q，并且保證 a[l?q?1]中的每個(gè)元素小于等于 a[q]，且 a[q] 小于等于 a[q+1?r]中的每個(gè)元素。所以只要某次劃分的 q 為第 k-1 個(gè)下標(biāo)的時(shí)候，我們就已經(jīng)找到了答案。 我們只關(guān)心這一點(diǎn)，至于 a[l?q?1]和 a[q+1?r]是否是有序的，我們不關(guān)心。

因此我們可以改進(jìn)快速排序算法來(lái)解決這個(gè)問(wèn)題：在分解的過(guò)程當(dāng)中，我們會(huì)對(duì)子數(shù)組進(jìn)行劃分，如果劃分得到的 q 正好就是我們需要的下標(biāo)，就直接返回 a[q]；否則，如果 q 比目標(biāo)下標(biāo)大，就遞歸左子區(qū)間，否則遞歸右子區(qū)間。這樣就可以把原來(lái)遞歸兩個(gè)區(qū)間變成只遞歸一個(gè)區(qū)間，提高了時(shí)間效率。這就是「快速選擇」算法。

我們知道快速排序的性能和「劃分」出的子數(shù)組的長(zhǎng)度密切相關(guān)。直觀地理解如果每次規(guī)模為 n 的問(wèn)題我們都劃分成 1 和 n?1，每次遞歸的時(shí)候又向 n?1的集合中遞歸，這種情況是最壞的，時(shí)間代價(jià)是 O(n ^ 2)。我們可以引入隨機(jī)化來(lái)加速這個(gè)過(guò)程，它的時(shí)間代價(jià)的期望是 O(n)，證明過(guò)程可以參考「《算法導(dǎo)論》9.2：期望為線性的選擇算法」。需要注意的是，這個(gè)時(shí)間復(fù)雜度只有在 隨機(jī)數(shù)據(jù) 下才成立，而對(duì)于精心構(gòu)造的數(shù)據(jù)則可能表現(xiàn)不佳。因此我們這里并沒(méi)有真正地使用隨機(jī)數(shù)，而是使用雙指針的方法，這種方法能夠較好地應(yīng)對(duì)各種數(shù)據(jù)。

注意，我最初使用填坑法來(lái)實(shí)現(xiàn)快排的時(shí)候，基準(zhǔn)值選擇的是最左邊的值，這樣對(duì)有非常多的重復(fù)元素的情況下超時(shí)，如示例40

代碼：

class Solution {
public:int quickSelect(vector<int>&nums,int left,int right,int k){int pivotIndex = left + std::rand() % (right - left + 1);  // 隨機(jī)選擇樞軸int pivotValue = nums[pivotIndex];std::swap(nums[pivotIndex], nums[left]); int i=left,j=right;while(i<j){while(i<j&&nums[j]<=pivotValue)j--;nums[i]=nums[j];while(i<j&&nums[i]>pivotValue)i++;nums[j]=nums[i];}nums[i]=pivotValue;if(i==k-1)return nums[i];else if(i<k-1) return quickSelect(nums,i+1,right,k);else return quickSelect(nums,left,i-1,k);}int findKthLargest(vector<int>& nums, int k) {return quickSelect(nums,0,nums.size()-1,k);}
};

時(shí)間復(fù)雜度:O(n)

空間復(fù)雜度：O(log?n)，遞歸使用?？臻g的空間代價(jià)的期望為 O(log?n)。

解法二：小根堆

c++的stl庫(kù)中的priority_queue可以實(shí)現(xiàn)小根隊(duì)

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int,vector<int>,greater<int>>que;for(auto n:nums){que.push(n);if(que.size()>k){que.pop();}}return que.top();}
};

時(shí)間復(fù)雜度：O(nlogn)

空間復(fù)雜度：O(n)

20. 75 顏色分類(lèi)

一開(kāi)始看到這道題，想的是直接一個(gè)調(diào)用STL庫(kù)的sort函數(shù)，一步到位，但是這明顯不是面試官想要的

解法一：單指針–交換排序

我們可以考慮對(duì)數(shù)組進(jìn)行兩次遍歷。在第一次遍歷中，我們將數(shù)組中所有的 0 交換到數(shù)組的頭部。在第二次遍歷中，我們將數(shù)組中所有的 1 交換到頭部的 0之后。此時(shí)，所有的 2 都出現(xiàn)在數(shù)組的尾部，這樣我們就完成了排序。

具體地，我們使用一個(gè)指針 ptr 表示當(dāng)前「頭部」指向的位置，初始化的時(shí)候ptr指向0的位置。

在第一次遍歷中，我們從左向右遍歷整個(gè)數(shù)組，如果找到了 0，那么就需要將 0 與ptr位置的元素進(jìn)行交換，并將ptr指針向后移動(dòng)一位。在遍歷結(jié)束之后，所有的 0 都被交換到「頭部」的范圍，并且「頭部」只包含 0，此時(shí)ptr指針指向所有的0之后的位置。

在第二次遍歷中，我們從當(dāng)前的ptr開(kāi)始遍歷整個(gè)數(shù)組，如果找到了 1，那么就需要將 1 與ptr位置的元素進(jìn)行交換，并將ptr指針向后移動(dòng)一位。在遍歷結(jié)束之后，所有的 1都被交換到「頭部」的范圍，并且都在 0 之后，此時(shí) 2 只出現(xiàn)在「頭部」之外的位置，因此排序完成。

代碼：

class Solution {
public:void sortColors(vector<int>& nums) {int n=nums.size();int ptr=0;for(int i=0;i<n;i++){if(nums[i]==0){swap(nums[i],nums[ptr]);ptr++;}}for(int i=ptr;i<n;i++){if(nums[i]==1){swap(nums[i],nums[ptr]);ptr++;}}}
};

• 時(shí)間復(fù)雜度：O(n)，其中 n是數(shù)組 nums的長(zhǎng)度。
• 空間復(fù)雜度：O(1)。

解法二：雙指針【最快】

p0指針用于替換0，p2指針用于替換2

考慮使用指針 p0來(lái)交換 0，p2來(lái)交換 2。此時(shí)，p0 的初始值仍然為 0，而 p2的初始值為 n?1。在遍歷的過(guò)程中，我們需要找出所有的 0 交換至數(shù)組的頭部，并且找出所有的 2 交換至數(shù)組的尾部。因此p0指針初始化時(shí)候指向數(shù)組的第一個(gè)元素，p2指針初始化時(shí)候指向數(shù)組的尾部；

由于此時(shí)其中一個(gè)指針 p2是從右向左移動(dòng)的，因此當(dāng)我們?cè)趶淖笙蛴冶闅v整個(gè)數(shù)組時(shí)，如果遍歷到的位置超過(guò)了 p2 ，那么就可以直接停止遍歷了。

具體地，我們從左向右遍歷整個(gè)數(shù)組，設(shè)當(dāng)前遍歷到的位置為 i，對(duì)應(yīng)的元素為 nums[i]；如果找到了 0，將其與 nums[p0] 進(jìn)行交換，并將 p0 向后移動(dòng)一個(gè)位置；

如果找到了 2，那么將其與 nums[p2]進(jìn)行交換，并將 p2向前移動(dòng)一個(gè)位置。

注意找到2的位置后，與nums[p2]進(jìn)行交換容易出錯(cuò)，對(duì)于第二種情況，當(dāng)我們將 nums[i]與 nums[p2 進(jìn)行交換之后，新的 nums[i]可能仍然是 2，也可能是 0。然而此時(shí)我們已經(jīng)結(jié)束了交換，開(kāi)始遍歷下一個(gè)元素 nums[i+1]，不會(huì)再考慮 nums[i]了，這樣我們就會(huì)得到錯(cuò)誤的答案。

因此，當(dāng)我們找到 2 時(shí)，我們需要不斷地將其與 nums[p2] 進(jìn)行交換，直到新的 nums[i]不為 2。此時(shí)，如果 nums[i] 為 0，那么對(duì)應(yīng)著第一種情況；如果 nums[i] 為 1，那么就不需要進(jìn)行任何后續(xù)的操作。

代碼：

class Solution {
public:void sortColors(vector<int>& nums) {int n=nums.size();int p0=0,p2=n-1;for(int i=0;i<=p2;i++){while(i<=p2&&nums[i]==2){swap(nums[i],nums[p2]);--p2;}if(nums[i]==0){swap(nums[i],nums[p0]);p0++;}}}
};

• 時(shí)間復(fù)雜度：O(n)，其中 nnn 是數(shù)組 nums* 的長(zhǎng)度。
• 空間復(fù)雜度：O(1)。

解法三：雙指針，同時(shí)找到0和1的位置，見(jiàn)官方題解75. 顏色分類(lèi) - 力扣（LeetCode）

21. 324 擺動(dòng)順序II

解法一：排序+雙指針

先將數(shù)組進(jìn)行排序，然后再通過(guò)雙指針逐個(gè)插入，我們將排序好的元素分成兩部分，左半部分是較小的元素，右半部分是較大元素，然后用兩個(gè)指針都指向兩部分的右側(cè)，采用先插入left指針指向的元素，再插入right指針指向的元素來(lái)達(dá)到搖擺的目的，一小一大。

代碼：

class Solution {
public:void wiggleSort(vector<int>& nums) {vector<int>arr(nums);sort(arr.begin(),arr.end());int left=(nums.size()-1)/2,right=nums.size()-1;for(int i=0;i<nums.size();i++){if(i%2==0){nums[i]=arr[left];left--;}else{nums[i]=arr[right];right--;}}}
};

時(shí)間復(fù)雜度：O(nlogn)，排序所需的時(shí)間復(fù)雜度是O(nlogn)，插入O(n)，整體O(nlogn)
空間復(fù)雜度：O(n)，需要額外的空間存放排序的元素。

方法二：三向切分，見(jiàn)官方題解

方法三：索引轉(zhuǎn)換

方法四：遞歸優(yōu)化

見(jiàn)官方題解：

324. 擺動(dòng)排序 II - 力扣（LeetCode）

22. 517 超級(jí)洗衣機(jī)[未解]

解法：貪心

見(jiàn)官方題解：517. 超級(jí)洗衣機(jī) - 力扣（LeetCode）

class Solution {
public:int findMinMoves(vector<int>& machines) {int tot=accumulate(machines.begin(),machines.end(),0);int n=machines.size();if(tot%n){return -1;}int avg=tot/n;int ans=0,sum=0;for(int num:machines){num-=avg;sum+=num;ans=max(ans,max(abs(sum),num));}return ans;}
};

時(shí)間復(fù)雜度：O(n)，其中 n 是數(shù)組machines 的長(zhǎng)度。

空間復(fù)雜度：O(1)。只需要常數(shù)的空間存放若干變量。

23. 649 Dota2 參議院

解法：貪心+循環(huán)隊(duì)列

思路與算法

我們以天輝方的議員為例。當(dāng)一名天輝方的議員行使權(quán)利時(shí)：

如果目前所有的議員都為天輝方，那么該議員可以直接宣布天輝方取得勝利；

如果目前仍然有夜魘方的議員，那么這名天輝方的議員只能行使「禁止一名參議員的權(quán)利」這一項(xiàng)權(quán)利。顯然，該議員不會(huì)令一名同為天輝方的議員喪失權(quán)利，所以他一定會(huì)挑選一名夜魘方的議員。那么應(yīng)該挑選哪一名議員呢**？容易想到的是，應(yīng)該貪心地挑選按照投票順序的下一名夜魘方的議員。這也是很容易形象化地證明的：既然只能挑選一名夜魘方的議員，那么就應(yīng)該挑最早可以進(jìn)行投票的那一名議員；如果挑選了其他較晚投票的議員，那么等到最早可以進(jìn)行投票的那一名議員行使權(quán)利時(shí)，一名天輝方議員就會(huì)喪失權(quán)利，這樣就得不償失了。**

由于我們總要挑選投票順序最早的議員，因此我們可以使用兩個(gè)隊(duì)列 radiant 和 dire 分別按照投票順序存儲(chǔ)天輝方和夜魘方每一名議員的投票時(shí)間。隨后我們就可以開(kāi)始模擬整個(gè)投票的過(guò)程：

如果此時(shí) radiant 或者 dire 為空，那么就可以宣布另一方獲得勝利；

如果均不為空，那么比較這兩個(gè)隊(duì)列的首元素，就可以確定當(dāng)前行使權(quán)利的是哪一名議員。如果radiant 的首元素較小，那說(shuō)明輪到天輝方的議員行使權(quán)利，其會(huì)挑選 dire 的首元素對(duì)應(yīng)的那一名議員。因此，我們會(huì)將 dire 的首元素永久地彈出，并將radiant 的首元素彈出，增加 n 之后再重新放回隊(duì)列，這里 n 是給定的字符串senate 的長(zhǎng)度，即表示該議員會(huì)參與下一輪的投票。

同理，如果 dire 的首元素較小，那么會(huì)永久彈出 radiant 的首元素，剩余的處理方法也是類(lèi)似的。

這樣一來(lái)，我們就模擬了整個(gè)投票的過(guò)程，也就可以得到最終的答案了。

class Solution {
public:string predictPartyVictory(string senate) {queue<int>radiant,dire;int n=senate.size();for(int i=0;i<n;i++){if(senate[i]=='R')radiant.push(i);elsedire.push(i);}while(!radiant.empty()&&!dire.empty()){if(radiant.front()<dire.front()){radiant.push(radiant.front()+n);radiant.pop();dire.pop();}else{dire.push(dire.front()+n);dire.pop();radiant.pop();}}return !radiant.empty()?"Radiant":"Dire";}
};

時(shí)間復(fù)雜度：O(n)，其中 n 是字符串 senate 的長(zhǎng)度。在模擬整個(gè)投票過(guò)程的每一步，我們進(jìn)行的操作的時(shí)間復(fù)雜度均為 O(1)，并且會(huì)彈出一名天輝方或夜魘方的議員。由于議員的數(shù)量為 n，因此模擬的步數(shù)不會(huì)超過(guò) n，時(shí)間復(fù)雜度即為 O(n)。

空間復(fù)雜度：O(n)，即為兩個(gè)隊(duì)列需要使用的空間。

24. 678 有效的括號(hào)字符串

解法一：雙棧

• 首先取得兩個(gè)棧st1,st2,st1存放的是左括號(hào)的索引，st2存放的是右括號(hào)的索引；
• 遍歷字符串?dāng)?shù)組，如果是左括號(hào)，則入棧st1；如果是星號(hào)則入棧st2;
• 如果是右括號(hào)，優(yōu)先將st1中的左括號(hào)彈出，與右括號(hào)匹配;如果左括號(hào)棧為空的條件下，會(huì)彈出星號(hào)棧的星號(hào)，作為匹配的左括號(hào)
• 最后左括號(hào)棧和星號(hào)?？赡懿粸榭?#xff0c;那么則檢驗(yàn)左括號(hào)棧中與星號(hào)棧是否可以匹配，注意到此時(shí)星號(hào)棧的索引號(hào)必須大于左括號(hào)棧，才能使得左括號(hào)和星號(hào)匹配

代碼：

class Solution {
public:bool checkValidString(string s) {stack<int>st1;//(棧stack<int>st2;//* 棧for(int i=0;i<s.size();i++){if(s[i]=='(')st1.push(i);else if(s[i]=='*')st2.push(i);else{if(!st1.empty()){st1.pop();}else if(!st2.empty()){st2.pop();}elsereturn false;}}if(st1.empty())return true;else{//注意左括下標(biāo)必須小于星號(hào)下標(biāo)while(!st1.empty()){if(!st2.empty()&&st1.top()<st2.top()){st1.pop();st2.pop();}else{return false;}}return true;}}
};

解法二：動(dòng)態(tài)規(guī)劃

見(jiàn)官方題解：678. 有效的括號(hào)字符串 - 力扣（LeetCode）

要判斷 s 是否為有效的括號(hào)字符串，需要判斷 s 的首尾字符以及 s 的中間字符是否符合有效的括號(hào)字符串的要求?？梢允褂脛?dòng)態(tài)規(guī)劃求解。

假設(shè)字符串 s 的長(zhǎng)度為 n。定義$\textit{dp}[i][j] $表示字符串 s 從下標(biāo) i 到 j 的子串是否為有效的括號(hào)字符串，其中 0≤i≤j<n。

動(dòng)態(tài)規(guī)劃的邊界情況是子串的長(zhǎng)度為 1或 2 的情況。

當(dāng)子串的長(zhǎng)度為 1 時(shí)，只有當(dāng)該字符是 ‘*’ 時(shí)，才是有效的括號(hào)字符串，此時(shí)子串可以看成空字符串；

當(dāng)子串的長(zhǎng)度為 2 時(shí)，只有當(dāng)兩個(gè)字符是 $\text{“()"},\text{“(*"},\text{“*)"},\text{“**"}$ 中的一種情況時(shí)，才是有效的括號(hào)字符串，此時(shí)子串可以看成 $\text{``()"}
$。

當(dāng)子串的長(zhǎng)度大于 2 時(shí)，需要根據(jù)子串的首尾字符以及中間的字符判斷子串是否為有效的括號(hào)字符串。字符串 s 從下標(biāo) i到 j 的子串的長(zhǎng)度大于 2 等價(jià)于 j?i≥2，此時(shí) $\text{dp}[i][j]$的計(jì)算如下，只要滿足以下一個(gè)條件就有$\text{dp}[i][j]=\text{true}$：

如果 s[i] 和 s[j] 分別為左括號(hào)和右括號(hào)，或者為 ‘*’，則當(dāng) $\text{dp}[i+1][j?1]=\text{true}$ 時(shí)，$\text{dp}[i][j]=\text{true}$，此時(shí) s[i]和 s[j] 可以分別看成左括號(hào)和右括號(hào)；

如果存在 i≤k<j 使得 $\text{dp}[i][k]$和$\text{dp}[k+1][j]$都為 true，則 $\text{dp}[i][j]=\text{true}$，因?yàn)樽址?s的下標(biāo)范圍[i,k] 和 [k+1,j] 的子串分別為有效的括號(hào)字符串，將兩個(gè)子串拼接之后的子串也為有效的括號(hào)字符串，對(duì)應(yīng)下標(biāo)范圍 [i,j]。

上述計(jì)算過(guò)程為從較短的子串的結(jié)果得到較長(zhǎng)的子串的結(jié)果，因此需要注意動(dòng)態(tài)規(guī)劃的計(jì)算順序。最終答案為 $\text{dp}[0][n?1]$。

代碼：

class Solution {
public:bool checkValidString(string s) {int n=s.size();vector<vector<bool>>dp(n,vector<bool>(n,false));for(int i=0;i<n;i++){if(s[i]=='*'){dp[i][i]=true;}}for(int i=1;i<n;i++){char c1=s[i-1];char c2=s[i];if((c1=='('&&c2==')')||(c1=='('&&c2=='*')||(c1=='*'&&c2==')')||(c1=='*'&&c2=='*'))dp[i-1][i]=true;}for(int i=n-3;i>=0;i--){char c1=s[i];for(int j=i+2;j<n;j++){char c2=s[j];if((c1=='('||c1=='*')&&(c2==')'||c2=='*')){dp[i][j]=dp[i+1][j-1];}for(int k=i;k<j&&!dp[i][j];k++){dp[i][j]=dp[i][k]&&dp[k+1][j];}}}return dp[0][n-1];}
};

時(shí)間復(fù)雜度：O(n3)，其中 n是字符串 s 的長(zhǎng)度。動(dòng)態(tài)規(guī)劃的狀態(tài)數(shù)是 O(n2)，每個(gè)狀態(tài)的計(jì)算時(shí)間最多為 O(n)。

空間復(fù)雜度：O(n2)，其中 n 是字符串 s 的長(zhǎng)度。創(chuàng)建了 n 行 n 列的二維數(shù)組 dp

解法三：貪心

見(jiàn)官方題解：678. 有效的括號(hào)字符串 - 力扣（LeetCode）

使用貪心的思想，可以將空間復(fù)雜度降到 O(1)。

從左到右遍歷字符串，遍歷過(guò)程中，未匹配的左括號(hào)數(shù)量可能會(huì)出現(xiàn)如下變化：

如果遇到左括號(hào)，則未匹配的左括號(hào)數(shù)量加 1；

如果遇到右括號(hào)，則需要有一個(gè)左括號(hào)和右括號(hào)匹配，因此未匹配的左括號(hào)數(shù)量減 1；

如果遇到星號(hào)，由于星號(hào)可以看成左括號(hào)、右括號(hào)或空字符串，因此未匹配的左括號(hào)數(shù)量可能加 1、減 1 或不變。

基于上述結(jié)論，可以在遍歷過(guò)程中維護(hù)未匹配的左括號(hào)數(shù)量可能的最小值和最大值，根據(jù)遍歷到的字符更新最小值和最大值：

如果遇到左括號(hào)，則將最小值和最大值分別加 1；

如果遇到右括號(hào)，則將最小值和最大值分別減 1；

如果遇到星號(hào)，則將最小值減 1，將最大值加 1。

任何情況下，未匹配的左括號(hào)數(shù)量必須非負(fù)，因此當(dāng)最大值變成負(fù)數(shù)時(shí)，說(shuō)明沒(méi)有左括號(hào)可以和右括號(hào)匹配，返回 false。

當(dāng)最小值為 0 時(shí)，不應(yīng)將最小值繼續(xù)減少，以確保最小值非負(fù)。

遍歷結(jié)束時(shí)，所有的左括號(hào)都應(yīng)和右括號(hào)匹配，因此只有當(dāng)最小值為 0 時(shí)，字符串 s 才是有效的括號(hào)字符串。

class Solution {
public:bool checkValidString(string s) {int minCount=0,maxCount=0;//記錄未匹配的左括號(hào)的個(gè)數(shù)的最小值和最大值int n=s.size();for(int i=0;i<n;i++){char c=s[i];if(c=='('){minCount++;maxCount++;}else if(c==')'){maxCount--;minCount=max(minCount-1,0);if(maxCount<0){return false;}}else{maxCount++;minCount=max(minCount-1,0);}}return minCount==0;}
};

• 時(shí)間復(fù)雜度：O(n)，其中 n 是字符串 s 的長(zhǎng)度。需要遍歷字符串一次。
• 空間復(fù)雜度：O(1)。

25. 420 強(qiáng)密碼檢驗(yàn)器

解法：這道題比較麻煩的模擬，并且沒(méi)什么意義

解法見(jiàn)官方題解：420. 強(qiáng)密碼檢驗(yàn)器 - 力扣（LeetCode）

代碼：

class Solution {
public:int strongPasswordChecker(string password) {int n = password.size();bool has_lower = false, has_upper = false, has_digit = false;for (char ch: password) {if (islower(ch)) {has_lower = true;}else if (isupper(ch)) {has_upper = true;}else if (isdigit(ch)) {has_digit = true;}}int categories = has_lower + has_upper + has_digit;if (n < 6) {return max(6 - n, 3 - categories);}else if (n <= 20) {int replace = 0;int cnt = 0;char cur = '#';for (char ch: password) {if (ch == cur) {++cnt;}else {replace += cnt / 3;cnt = 1;cur = ch;}}replace += cnt / 3;return max(replace, 3 - categories);}else {// 替換次數(shù)和刪除次數(shù)int replace = 0, remove = n - 20;// k mod 3 = 1 的組數(shù)，即刪除 2 個(gè)字符可以減少 1 次替換操作int rm2 = 0;int cnt = 0;char cur = '#';for (char ch: password) {if (ch == cur) {++cnt;}else {if (remove > 0 && cnt >= 3) {if (cnt % 3 == 0) {// 如果是 k % 3 = 0 的組，那么優(yōu)先刪除 1 個(gè)字符，減少 1 次替換操作--remove;--replace;}else if (cnt % 3 == 1) {// 如果是 k % 3 = 1 的組，那么存下來(lái)備用++rm2;}// k % 3 = 2 的組無(wú)需顯式考慮}replace += cnt / 3;cnt = 1;cur = ch;}}if (remove > 0 && cnt >= 3) {if (cnt % 3 == 0) {--remove;--replace;}else if (cnt % 3 == 1) {++rm2;}}replace += cnt / 3;// 使用 k % 3 = 1 的組的數(shù)量，由剩余的替換次數(shù)、組數(shù)和剩余的刪除次數(shù)共同決定int use2 = min({replace, rm2, remove / 2});replace -= use2;remove -= use2 * 2;// 由于每有一次替換次數(shù)就一定有 3 個(gè)連續(xù)相同的字符（k / 3 決定），因此這里可以直接計(jì)算出使用 k % 3 = 2 的組的數(shù)量int use3 = min({replace, remove / 3});replace -= use3;remove -= use3 * 3;return (n - 20) + max(replace, 3 - categories);}}
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

26. 53 最大子數(shù)組和

解法一：動(dòng)態(tài)規(guī)劃【步驟】

• 定義dp[i]表示數(shù)組中前i+1（注意這里的i是從0開(kāi)始的）個(gè)元素構(gòu)成的連續(xù)子數(shù)組的最大和。
• 如果要計(jì)算前i+1個(gè)元素構(gòu)成的連續(xù)子數(shù)組的最大和，也就是計(jì)算dp[i]，只需要判斷dp[i-1]+num[i]和num[i]哪個(gè)大，如果dp[i-1]+num[i]大，則dp[i]=dp[i-1]+num[i]，否則令dp[i]=nums[i]。
• 在遞推過(guò)程中，可以設(shè)置一個(gè)值max，用來(lái)保存子序列的最大值，最后返回即可。
• 轉(zhuǎn)移方程：dp[i]=Math.max(nums[i], nums[i]+dp[i-1])；
• 邊界條件判斷，當(dāng)i等于0的時(shí)候，也就是前1個(gè)元素，他能構(gòu)成的最大和也就是他自己，所以dp[0]=num[0];

代碼：

class Solution {
public:int maxSubArray(vector<int>& nums) {int res=nums[0];int n=nums.size();vector<int>dp(nums);for(int i=1;i<n;i++){dp[i]=max(dp[i],dp[i-1]+nums[i]);res=max(res,dp[i]);}return res;}
};

時(shí)間復(fù)雜度：O(n)，其中 n 為 nums 數(shù)組的長(zhǎng)度。我們只需要遍歷一遍數(shù)組即可求得答案。
空間復(fù)雜度：O(1)。我們只需要常數(shù)空間存放若干變量。

解法二：分治法

分治法的思路是這樣的，其實(shí)也是分類(lèi)討論。

連續(xù)子序列的最大和主要由這三部分子區(qū)間里元素的最大和得到：

第 1 部分：子區(qū)間 [left, mid]；
第 2 部分：子區(qū)間 [mid + 1, right]；
第 3 部分：包含子區(qū)間 [mid , mid + 1] 的子區(qū)間，即 nums[mid] 與 nums[mid + 1] 一定會(huì)被選取。
對(duì)這三個(gè)部分求最大值即可。

說(shuō)明：考慮第 3 部分跨越兩個(gè)區(qū)間的連續(xù)子數(shù)組的時(shí)候，由于 nums[mid] 與 nums[mid + 1] 一定會(huì)被選取，可以從中間向兩邊擴(kuò)散，擴(kuò)散到底 選出最大值。

代碼：

class Solution {
public:int maxSubArray(vector<int>& nums) {int len=nums.size();if(len==0)return 0;return maxSubArraySum(nums,0,len-1);}int maxCrossingSum(vector<int>& nums,int left,int mid,int right){//一定包含nums[mid]元素int sum=0;int leftSum=-1e6;//左半邊包含nums[mid]元素，最多可以到達(dá)的地方for(int i=mid;i>=left;i--){sum+=nums[i];if(sum>leftSum){leftSum=sum;}}sum=0;int rightsum=-1e6;for(int i=mid+1;i<=right;i++){sum+=nums[i];if(sum>rightsum){rightsum=sum;}}return leftSum+rightsum;}int maxSubArraySum(vector<int>& nums,int left,int right){if(left==right)return nums[left];int mid=left+(right-left)/2;return max3(maxSubArraySum(nums,left,mid),maxSubArraySum(nums,mid+1,right),maxCrossingSum(nums,left,mid,right));}int max3(int num1,int num2,int num3){return max(num1,max(num2,num3));}};

時(shí)間復(fù)雜度：O(Nlog?N)，這里遞歸的深度是對(duì)數(shù)級(jí)別的，每一層需要遍歷一遍數(shù)組（或者數(shù)組的一半、四分之一）；
空間復(fù)雜度：O(log?N)，需要常數(shù)個(gè)變量用于選取最大值，需要使用的空間取決于遞歸棧的深度.

27. 134 加油站

解法：貪心+一次遍歷

最容易想到的解法就是一次遍歷，從頭到尾遍歷每個(gè)加油站，并檢查該加油站為起點(diǎn)，最終能否行駛一周。我們可以通過(guò)減少被檢查的加油站數(shù)目，來(lái)降低總的時(shí)間復(fù)雜度。

即假設(shè)從x開(kāi)始行駛，無(wú)法到達(dá)y的下一站，那么[x,y]的中間某一點(diǎn)為起始點(diǎn)也肯定無(wú)法到達(dá)y的下一站，官方題解中包含詳細(xì)證明：

134. 加油站 - 力扣（LeetCode）

直觀的理解：如果能從x到達(dá)y的話，那么從x到達(dá)(x,y)中間任何一站時(shí)剩余的油量肯定都是>=0的，否則便無(wú)法一直到達(dá)y。

舉例，從a出發(fā)，經(jīng)過(guò)b，到達(dá)c，油量不夠無(wú)法到達(dá)d。從a到達(dá)b的時(shí)候，剩余油量最壞的情況也是=0，而如果直接從b出發(fā)，初始油量只能=0。從a出發(fā)，在到達(dá)b點(diǎn)的時(shí)候油量還能>=0，無(wú)法到達(dá)d點(diǎn)；而如果直接從b點(diǎn)出發(fā)，此時(shí)初始油量=0，就更不可能到達(dá)d點(diǎn)了。

因此，在一次遍歷起始點(diǎn)的時(shí)候，假如x為起始點(diǎn)，遍歷到y(tǒng)時(shí)，無(wú)法到達(dá)y的下一個(gè)節(jié)點(diǎn)；那么下次遍歷的起點(diǎn)就可以改為y+1

代碼：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int i=0;int n=gas.size();while(i<n){int sumGas=0,sumCost=0;int cnt=0;while(cnt<n){int j=(i+cnt)%n;sumGas+=gas[j];sumCost+=cost[j];if(sumCost>sumGas){break;}cnt++;}if(cnt==n){return i;}elsei=i+cnt+1;}return -1;}
};

• 時(shí)間復(fù)雜度：O(N)，其中 N 為數(shù)組的長(zhǎng)度。我們對(duì)數(shù)組進(jìn)行了單次遍歷。
• 空間復(fù)雜度：O(1)。

28. 581 最短無(wú)序連續(xù)子數(shù)組

解法一：貪心+雙指針+一次遍歷

• 我們把整個(gè)數(shù)組分成三段處理。

• 起始時(shí)，先通過(guò)雙指針 left 和 right 找到左右兩次側(cè)滿足 單調(diào)遞增 的分割點(diǎn)。

  • 即從left從左到右遍歷，找到nums[left]>nums[left+1]的索引left
  • 從right從右向左遍歷，找到nums[right]<nums[right-1]的索引right
  • 即此時(shí) [0,left] 和 [right,n) 滿足升序要求，而中間部分 (left,right) 不確保有序。

• 然后我們對(duì)中間部分 [left,right] 進(jìn)行遍歷：

  因?yàn)槲覀冎酪沟弥虚g部分排序后整體升序的話，要保證中間部分的所有數(shù)都大于nums[left-1]【即第一塊升序部分】，中間部分的所有數(shù)要小于nums[right+1]【即第三塊的升序部分】

• 遍歷中間部分，若發(fā)現(xiàn) nums[x]<nums[left?1]由于對(duì) [left,right] 部分進(jìn)行排序后 nums[x] 會(huì)出現(xiàn)在 nums[left?1] 后，將不滿足整體升序，此時(shí)我們需要調(diào)整分割點(diǎn) left 的位置；即向前移動(dòng)直到nums[x]小于此時(shí)的nums[left-1];

• 若發(fā)現(xiàn) nums[x]>nums[right+1]：由于對(duì)[left,right] 部分進(jìn)行排序后 nums[x 會(huì)出現(xiàn)在 nums[right+1]前，將不滿足整體升序，此時(shí)我們需要調(diào)整分割點(diǎn) right 的位置。

代碼：

class Solution {
public:int MIN=-1e5,MAX=1e5;int findUnsortedSubarray(vector<int>& nums) {int left=0;int right=nums.size()-1;while(left<nums.size()-1){if(nums[left]>nums[left+1]){break;}left++;}if(left==nums.size()-1)return 0;while(right>0){if(nums[right]<nums[right-1]){break;}right--;}int l=left,r=right;//繼續(xù)調(diào)整中間情況for(int i=l;i<=r;i++){while(left>=1&&nums[i]<nums[left-1])left--;while(right<nums.size()-1&&nums[i]>nums[right+1])right++;}return right==left?0:(right-left+1);}
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

解法二：簡(jiǎn)單排序

見(jiàn)官方題解：排序之后與原數(shù)組不相同的左右指針位置即為中間數(shù)組的長(zhǎng)度

• C++ is_sorted()函數(shù)

此函數(shù)專(zhuān)門(mén)用于判斷某個(gè)序列是否為有序序列。
和之前學(xué)習(xí)的其它排序函數(shù)（比如 sorted() 函數(shù)）一樣，is_sorted() 函數(shù)本質(zhì)上就是一個(gè)函數(shù)模板，定義在頭文件中。因?yàn)?#xff0c;在使用該函數(shù)之前，程序中必須先引入此頭文件。

is_sorted() 函數(shù)有 2 種語(yǔ)法格式，分別是：

//判斷 [first, last) 區(qū)域內(nèi)的數(shù)據(jù)是否符合 std::less<T> 排序規(guī)則，即是否為升序序列
bool is_sorted (ForwardIterator first, ForwardIterator last);
//判斷 [first, last) 區(qū)域內(nèi)的數(shù)據(jù)是否符合 comp 排序規(guī)則  
bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);

代碼：

class Solution {
public:int findUnsortedSubarray(vector<int>& nums) {if(is_sorted(nums.begin(),nums.end())){return 0;}vector<int>numsSorted(nums);sort(numsSorted.begin(),numsSorted.end());int left=0;while(nums[left]==numsSorted[left])left++;int right=nums.size()-1;while(nums[right]==numsSorted[right]){right--;}return right-left+1;    }
};

時(shí)間復(fù)雜度：O(nlog?n)，其中 n 為給定數(shù)組的長(zhǎng)度。我們需要 O(nlog?n) 的時(shí)間進(jìn)行排序，以及 O(n)的時(shí)間遍歷數(shù)組，因此總時(shí)間復(fù)雜度為 O(n)。

空間復(fù)雜度：O(n，其中 n 為給定數(shù)組的長(zhǎng)度。我們需要額外的一個(gè)數(shù)組保存排序后的數(shù)組numsSorted。

29. 152 乘積最大子數(shù)組

解法：動(dòng)態(tài)規(guī)劃

思路和算法

如果我們用 fmax?(i)來(lái)表示以第 i個(gè)元素結(jié)尾的乘積最大子數(shù)組的乘積，a 表示輸入?yún)?shù) nums，那么根據(jù)「53. 最大子序和」的經(jīng)驗(yàn)，我們很容易推導(dǎo)出這樣的狀態(tài)轉(zhuǎn)移方程：

f max ? ( i ) = max ? i = 1 n { f ( i ? 1 ) × a i , a i } f_{\max}(i) = \max_{i = 1}^{n} \{ f(i - 1) \times a_i, a_i \} fmax?(i)=maxi=1n?{f(i?1)×ai?,ai?}

它表示以第 i個(gè)元素結(jié)尾的乘積最大子數(shù)組的乘積可以考慮 $a_i$加入前面的 $f_{\max }(i?1)$對(duì)應(yīng)的一段，或者單獨(dú)成為一段，這里兩種情況下取最大值。求出所有的 $f_{\max }(i)$ 之后選取最大的一個(gè)作為答案。

可是在這里，這樣做是錯(cuò)誤的。為什么呢？

因?yàn)檫@里的定義并不滿足「最優(yōu)子結(jié)構(gòu)」。具體地講，如果 a = { 5 , 6 , ? 3 , 4 , ? 3 } a = \{ 5, 6, -3, 4, -3 \} a={5,6,?3,4,?3}，那么此時(shí) ?$f_{\max }$對(duì)應(yīng)的序列是 { 5 , 30 , ? 3 , 4 , ? 3 } \{ 5, 30, -3, 4, -3 \} {5,30,?3,4,?3}，按照前面的算法我們可以得到答案為 30，即前兩個(gè)數(shù)的乘積，而實(shí)際上答案應(yīng)該是全體數(shù)字的乘積。我們來(lái)想一想問(wèn)題出在哪里呢？問(wèn)題出在最后一個(gè) ?3 所對(duì)應(yīng)$f_{\max }$的值既不是 ?3，也不是 4×(?3)，而是 5×6×(?3)×4×(?3)。所以我們得到了一個(gè)結(jié)論：當(dāng)前位置的最優(yōu)解未必是由前一個(gè)位置的最優(yōu)解轉(zhuǎn)移得到的。

我們可以根據(jù)正負(fù)性進(jìn)行分類(lèi)討論。

考慮當(dāng)前位置如果是一個(gè)負(fù)數(shù)的話，那么我們希望以它前一個(gè)位置結(jié)尾的某個(gè)段的積也是個(gè)負(fù)數(shù)，這樣就可以負(fù)負(fù)得正，并且我們希望這個(gè)積盡可能「負(fù)得更多」，即盡可能小。如果當(dāng)前位置是一個(gè)正數(shù)的話，我們更希望以它前一個(gè)位置結(jié)尾的某個(gè)段的積也是個(gè)正數(shù)，并且希望它盡可能地大。于是這里我們可以再維護(hù)一個(gè) $f_{\min }(i)$，它表示以第 i 個(gè)元素結(jié)尾的乘積最小子數(shù)組的乘積，那么我們可以得到這樣的動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程：

f max ? ( i ) = max ? i = 1 n { f max ? ( i ? 1 ) × a i , f min ? ( i ? 1 ) × a i , a i } f min ? ( i ) = min ? i = 1 n { f max ? ( i ? 1 ) × a i , f min ? ( i ? 1 ) × a i , a i } \begin{aligned} f_{\max}(i) &= \max_{i = 1}^{n} \{ f_{\max}(i - 1) \times a_i, f_{\min}(i - 1) \times a_i, a_i \} \\ f_{\min}(i) &= \min_{i = 1}^{n} \{ f_{\max}(i - 1) \times a_i, f_{\min}(i - 1) \times a_i, a_i \} \end{aligned} fmax?(i)fmin?(i)?=i=1maxn?{fmax?(i?1)×ai?,fmin?(i?1)×ai?,ai?}=i=1minn?{fmax?(i?1)×ai?,fmin?(i?1)×ai?,ai?}?

它代表第 i 個(gè)元素結(jié)尾的乘積最大子數(shù)組的乘積 $f_{\max }(i)$，可以考慮把 $a_i$ 加入第 i?1 個(gè)元素結(jié)尾的乘積最大或最小的子數(shù)組的乘積中，二者加上 $a_i$，三者取大，就是第 i個(gè)元素結(jié)尾的乘積最大子數(shù)組的乘積。第 i個(gè)元素結(jié)尾的乘積最小子數(shù)組的乘積 $f_{\min }(i)$

max_element()和 min_element（）函數(shù)簡(jiǎn)介

max_element（）與min_element（）分別用來(lái)求最大元素和最小元素的位置。

• 接收參數(shù)：容器的首尾地址（迭代器）（可以是一個(gè)區(qū)間）
• 返回：最值元素的地址（迭代器），需要減去序列頭以轉(zhuǎn)換為下標(biāo)

代碼：

class Solution {
public:int maxProduct(vector<int>& nums) {vector<int>maxF(nums),minF(nums);int maxNum=nums[0];for(int i=1;i<nums.size();i++){maxF[i]=max(maxF[i-1]*nums[i],max(nums[i],minF[i-1]*nums[i]));if(maxF[i]>maxNum)maxNum=maxF[i];minF[i]=min(minF[i-1]*nums[i],min(nums[i],maxF[i-1]*nums[i]));}return maxNum;}
};

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

優(yōu)化方法：由于第 i個(gè)狀態(tài)只和第 i?1個(gè)狀態(tài)相關(guān)，根據(jù)「滾動(dòng)數(shù)組」思想，我們可以只用兩個(gè)變量來(lái)維護(hù) 、i?1 時(shí)刻的狀態(tài)，一個(gè)維護(hù) $f_{\max }$ ，一個(gè)維護(hù) $f_{\min }$

class Solution {
public:int maxProduct(vector<int>& nums) {int maxF=nums[0],minF=nums[0],ans=nums[0];for(int i=1;i<nums.size();i++){int mx=maxF;int mn= minF;maxF=max(mx*nums[i],max(nums[i],mn*nums[i]));minF = min(mn * nums[i], min(nums[i], mx * nums[i]));ans = max(maxF, ans);}return ans;}
};

30. 334 遞增的三元子序列

解法一：貪心

可以使用貪心的方法將空間復(fù)雜度降到 O(1)。從左到右遍歷數(shù)組 nums，遍歷過(guò)程中維護(hù)兩個(gè)變量first 和 second，分別表示遞增的三元子序列中的第一個(gè)數(shù)和第二個(gè)數(shù)，任何時(shí)候都有 first<second。

初始時(shí)，first=nums[0]，second=+∞。對(duì)于 1≤i<n，當(dāng)遍歷到下標(biāo) i 時(shí)，令 num=nums[i]，進(jìn)行如下操作：

如果 num>second，則找到了一個(gè)遞增的三元子序列，返回 true；

否則，如果 num>first，則將 second 的值更新為 num；

否則，將 first 的值更新為 num。

如果遍歷結(jié)束時(shí)沒(méi)有找到遞增的三元子序列，返回 false。

上述做法的貪心思想是：為了找到遞增的三元子序列，first 和second 應(yīng)該盡可能地小，此時(shí)找到遞增的三元子序列的可能性更大。

代碼：

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int n=nums.size();if(n<3)return false;int first=nums[0],second=INT_MAX;for(int i=1;i<n;i++){int num=nums[i];if(num>second)return true;else if(num>first){second=num;}else{first=num;}}return false;   }
};

時(shí)間復(fù)雜度：O(n)，其中 n 是數(shù)組 nums 的長(zhǎng)度。需要遍歷數(shù)組一次。

空間復(fù)雜度：O(1)

解法二：雙向遍歷

見(jiàn)官方題解：334. 遞增的三元子序列 - 力扣（LeetCode）

代碼：

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int n=nums.size();if(n<3)return false;vector<int>leftMin(n),rightMax(n);leftMin[0]=nums[0];rightMax[n-1]=nums[n-1];for(int i=1;i<n;i++){leftMin[i]=min(leftMin[i-1],nums[i]);} for(int i=n-2;i>=0;i--){rightMax[i]=max(rightMax[i+1],nums[i]);}for(int i=1;i<n-1;i++){if(nums[i]>leftMin[i-1]&&nums[i]<rightMax[i+1])return true;}return false;}
};

時(shí)間復(fù)雜度：O(n)，其中 n是數(shù)組 nums 的長(zhǎng)度。需要遍歷數(shù)組三次。

空間復(fù)雜度：O(n)，其中 n 是數(shù)組 nums 的長(zhǎng)度。需要?jiǎng)?chuàng)建兩個(gè)長(zhǎng)度為 n 的數(shù)組 leftMin 和 rightMax。

31. 376 擺動(dòng)序列

解法一：動(dòng)態(tài)規(guī)劃

本題大家都很容易想到用動(dòng)態(tài)規(guī)劃來(lái)求解，求解的過(guò)程類(lèi)似最長(zhǎng)上升子序列，不過(guò)是需要判斷兩個(gè)序列。大家在實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的平方復(fù)雜度時(shí)，就會(huì)考慮如何優(yōu)化到線性復(fù)雜度。

假設(shè) up[i] 表示 nums[0:i] 中最后兩個(gè)數(shù)字遞增的最長(zhǎng)擺動(dòng)序列長(zhǎng)度，down[i] 表示 nums[0:i] 中最后兩個(gè)數(shù)字遞減的最長(zhǎng)擺動(dòng)序列長(zhǎng)度，只有一個(gè)數(shù)字時(shí)默認(rèn)為 1。

接下來(lái)我們進(jìn)行分類(lèi)討論：

• nums[i+1] > nums[i]

  • 假設(shè) down[i] 表示的最長(zhǎng)擺動(dòng)序列的最遠(yuǎn)末尾元素下標(biāo)正好為 i，遇到新的上升元素后，up[i+1] = down[i] + 1 ，這是因?yàn)?up 一定從 down 中產(chǎn)生（初始除外），并且 down[i] 此時(shí)最大。

  • 假設(shè) down[i] 表示的最長(zhǎng)擺動(dòng)序列的最遠(yuǎn)末尾元素下標(biāo)小于 i，設(shè)為 j，那么 nums[j:i] 一定是遞增的，因?yàn)槿敉耆f減，最遠(yuǎn)元素下標(biāo)等于 i，若波動(dòng)，那么 down[i] > down[j]。由于 nums[j:i] 遞增，down[j:i] 一直等于 down[j] ，依然滿足 up[i+1] = down[i] + 1 。

• nums[i+1] < nums[i]，類(lèi)似第一種情況

• nums[i+1] == nums[i]，新的元素不能用于任何序列，保持不變

并且注意到： down 和 up 只和前一個(gè)狀態(tài)有關(guān)，所以我們可以優(yōu)化存儲(chǔ)，分別用一個(gè)變量即可。

代碼：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int up=1,down=1;if(nums.size()==0)return 0;for(int i=1;i<nums.size();i++){if(nums[i]>nums[i-1])up=down+1;else if(nums[i]<nums[i-1]){down=up+1;}    }return max(up,down);   }
};

時(shí)間復(fù)雜度：O(n)，其中 n 是序列的長(zhǎng)度。我們只需要遍歷該序列一次。

空間復(fù)雜度：O(1)。我們只需要常數(shù)空間來(lái)存放若干變量。

解法二：貪心

見(jiàn)題解：376. 擺動(dòng)序列 - 力扣（LeetCode）

代碼：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size()==1)return 1;if(nums.size()==2)return nums[0]==nums[1]?1:2;//2. up變量記錄趨勢(shì)往上還是往下int index=1;while(index<nums.size()&&nums[index]==nums[index-1]){index++;}if(index==nums.size())return 1;bool up=nums[index]>nums[index-1];//此時(shí)maxlen的長(zhǎng)度至少為2int maxlen=2,diff;for(int i=index+1;i<nums.size();i++){diff=nums[i]-nums[i-1];if((diff>0&&!up)||(diff<0&&up)){maxlen++;up=!up;}}return maxlen; }
};

32. 659 分割數(shù)組為連續(xù)子序列

解法一：貪心
首先使用兩個(gè)哈希表nc和tail

nc[i]：存儲(chǔ)原數(shù)組中數(shù)字i出現(xiàn)的次數(shù)
tail[i]：存儲(chǔ)以數(shù)字i結(jié)尾的且符合題意的連續(xù)子序列個(gè)數(shù)
先去尋找一個(gè)長(zhǎng)度為3的連續(xù)子序列 i, i+1, i+2，找到后就將 nc[i], nc[i+1], nc[i+2] 中對(duì)應(yīng)數(shù)字消耗1個(gè)（即-1），并將 tail[i+2] 加 1，即以 i+2 結(jié)尾的子序列個(gè)數(shù) +1。
如果后續(xù)發(fā)現(xiàn)有能夠接在這個(gè)連續(xù)子序列的數(shù)字 i+3，則延長(zhǎng)以 i+2 為結(jié)尾的連續(xù)子序列到 i+3，此時(shí)消耗 nc[i+3] 一個(gè)，由于子序列已延長(zhǎng)，因此tail[i+2] 減 1，tail[i+3] 加 1
在不滿足上面的情況下
如果 nc[i] 為 0，說(shuō)明這個(gè)數(shù)字已經(jīng)消耗完，可以不管了
如果 nc[i] 不為 0，說(shuō)明這個(gè)數(shù)字多出來(lái)了，且無(wú)法組成連續(xù)子序列，所以可以直接返回 false 了
因此，只有檢查到某個(gè)數(shù)時(shí)，這個(gè)數(shù)未被消耗完，且既不能和前面組成連續(xù)子序列，也不能和后面組成連續(xù)子序列時(shí)，無(wú)法分割

代碼：

class Solution {
public:bool isPossible(vector<int>& nums) {int n=nums.size();if(n<3)return false;unordered_map<int,int>nc,tail;for(auto num:nums){nc[num]++;}for(auto num:nums){if(nc[num]==0)continue;else if(nc[num]>0&&tail[num-1]>0){tail[num-1]--;tail[num]++;nc[num]--;}else if(nc[num]>0&&nc[num+1]>0&&nc[num+2]>0){nc[num]--;nc[num+1]--;nc[num+2]--;tail[num+2]++;}else{return false;}}return true;}
};

時(shí)間復(fù)雜度：O(N)，所有元素遍歷一遍 O(N)，循環(huán)內(nèi)部均為常數(shù)時(shí)間操作 O(1)
空間復(fù)雜度：O(N)，使用了兩個(gè)哈希 map

解法二：哈希表 + 最小堆

見(jiàn)官方題解：659. 分割數(shù)組為連續(xù)子序列 - 力扣（LeetCode）

33. 343 整數(shù)拆分

解法一：動(dòng)態(tài)規(guī)劃

對(duì)于正整數(shù) n，當(dāng) n≥2 時(shí)，可以拆分成至少兩個(gè)正整數(shù)的和。令 x 是拆分出的第一個(gè)正整數(shù)，則剩下的部分是 n?x，n?x可以不繼續(xù)拆分，或者繼續(xù)拆分成至少兩個(gè)正整數(shù)的和。由于每個(gè)正整數(shù)對(duì)應(yīng)的最大乘積取決于比它小的正整數(shù)對(duì)應(yīng)的最大乘積，因此可以使用動(dòng)態(tài)規(guī)劃求解。

創(chuàng)建數(shù)組 dp，其中 dp[i] 表示將正整數(shù) i拆分成至少兩個(gè)正整數(shù)的和之后，這些正整數(shù)的最大乘積。特別地，0 不是正整數(shù)，1 是最小的正整數(shù)，0 和 1 都不能拆分，因此 dp[1]=1;

當(dāng) i≥2 時(shí)，假設(shè)對(duì)正整數(shù) i拆分出的第一個(gè)正整數(shù)是 j（1≤j<i），則有以下兩種方案：

將 i 拆分成 j和 i?j 的和，且 i?j不再拆分成多個(gè)正整數(shù)，此時(shí)的乘積是 j×(i?j)；

將 i 拆分成 j 和 i?j 的和，且 i?j 繼續(xù)拆分成多個(gè)正整數(shù)，此時(shí)的乘積是 j×dp[i?j]。

因此，當(dāng) j 固定時(shí)，有 $\text{dp}[i]=\max (j\times (i?j),j\times \text{dp}[i?j])$。由于 j 的取值范圍是 1 到 i?1，需要遍歷所有的 j 得到 dp[i] 的最大值，因此可以得到狀態(tài)轉(zhuǎn)移方程如下：

dp [ i ] = max ? 1 ≤ j < i { max ? ( j × ( i ? j ) , j × dp [ i ? j ] ) } \textit{dp}[i]=\mathop{\max}\limits_{1 \le j < i}\{\max(j \times (i-j), j \times \textit{dp}[i-j])\} dp[i]=1≤j<imax?{max(j×(i?j),j×dp[i?j])}

最終得到 dp[n] 的值即為將正整數(shù) n 拆分成至少兩個(gè)正整數(shù)的和之后，這些正整數(shù)的最大乘積。

優(yōu)化版的動(dòng)態(tài)規(guī)劃見(jiàn)：343. 整數(shù)拆分 - 力扣（LeetCode）

解法二：數(shù)學(xué)推導(dǎo)

見(jiàn)：https://leetcode.cn/problems/integer-break/solutions/

拆分規(guī)則：
最優(yōu)： 3 。把數(shù)字 n 可能拆為多個(gè)因子 3 ，余數(shù)可能為 0,1,2 三種情況。
次優(yōu)： 2 。若余數(shù)為 2 ；則保留，不再拆為 1+1 。
最差： 1。若余數(shù)為 1 ；則應(yīng)把一份 3+1 替換為 2+2因?yàn)?2×2>3×1

34. 496 下一個(gè)更大元素I

解法一：雙重循環(huán)

最簡(jiǎn)單的方法就是對(duì)于nums1中的所有元素，遍歷nums2，找到其所在的位置，并且尋找該位置后是否有比其大的數(shù)，若有，則將此數(shù)字加入res數(shù)組，否則將-1加入res數(shù)組

代碼：

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int>res;for(int ns1:nums1){for(int i=0;i<nums2.size();i++){if(nums2[i]==ns1){int j=i;int greaterNs1=-1;while(j<nums2.size()){if(nums2[j]>ns1){greaterNs1=nums2[j];break;}j++;}res.push_back(greaterNs1);break;}}}return res;}
};

時(shí)間復(fù)雜度：O(mn)，其中 m 是 nums1的長(zhǎng)度，n是 nums2 的長(zhǎng)度。

空間復(fù)雜度：O(1)。

解法二： 單調(diào)棧+hash表

思路

我們可以先預(yù)處理 nums2 ，使查詢 nums1中的每個(gè)元素在 nums2中對(duì)應(yīng)位置的右邊的第一個(gè)更大的元素值時(shí)不需要再遍歷 nums2。于是，我們將題目分解為兩個(gè)子問(wèn)題：

第 1個(gè)子問(wèn)題：如何更高效地計(jì)算 nums2 中每個(gè)元素右邊的第一個(gè)更大的值；

第 2 個(gè)子問(wèn)題：如何存儲(chǔ)第 1 個(gè)子問(wèn)題的結(jié)果。

算法

我們可以使用單調(diào)棧來(lái)解決第 1 個(gè)子問(wèn)題。倒序遍歷 nums2，并用單調(diào)棧中維護(hù)當(dāng)前位置右邊的更大的元素列表，從棧底到棧頂?shù)脑厥菃握{(diào)遞減的。

具體地，每次我們移動(dòng)到數(shù)組中一個(gè)新的位置 i，就將當(dāng)前單調(diào)棧中所有小于 nums2的元素彈出單調(diào)棧，當(dāng)前位置右邊的第一個(gè)更大的元素即為棧頂元素，如果棧為空則說(shuō)明當(dāng)前位置右邊沒(méi)有更大的元素。隨后我們將位置 i的元素入棧。

細(xì)節(jié)

因?yàn)樵谶@道題中我們只需要用到 nums2 中元素的順序而不需要用到下標(biāo)，所以棧中直接存儲(chǔ) nums2中元素的值即可。

代碼：

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> numToGreater;stack<int>st;for(int i=nums2.size()-1;i>=0;i--){int n=nums2[i];while(!st.empty()&&st.top()<=n){st.pop();}if(st.empty())numToGreater[n]=-1;elsenumToGreater[n]=st.top();st.push(n);}vector<int>res(nums1.size());for(int i=0;i<nums1.size();i++){res[i]=numToGreater[nums1[i]];}return res;}
};

時(shí)間復(fù)雜度：O(m+n)，其中 m 是 nums1的長(zhǎng)度，n 是 nums2 的長(zhǎng)度。我們需要遍歷 nums2以計(jì)算 nums2中每個(gè)元素右邊的第一個(gè)更大的值；需要遍歷 nums1 以生成查詢結(jié)果。

空間復(fù)雜度：O(n)，用于存儲(chǔ)哈希表。

35. 503 下一個(gè)更大的元素||

解法一：簡(jiǎn)單模擬

即我們利用取模來(lái)作為循環(huán)數(shù)組的循環(huán)，對(duì)于nums中的每一個(gè)元素，若是從這個(gè)元素后一個(gè)元素循環(huán)回到當(dāng)前元素都未找到比它大的數(shù)，則將-1加入解，否則將得到的比當(dāng)前元素大的值加入解。

代碼：

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int>res(nums.size(),-1);int n=nums.size();for(int i=0;i<n;i++){int cnt=1;int j=(i+1)%n;while(cnt<n){if(nums[j]>nums[i]){res[i]=nums[j];break;}j=(j+1)%n;cnt++;}}return res;}
};

時(shí)間復(fù)雜度：O(n^2)

空間復(fù)雜度：O(1)

解法二：利用496做法中的單調(diào)棧+循環(huán)數(shù)組

本題如果暴力求解，對(duì)于每個(gè)元素都向后去尋找比它更大的元素，那么時(shí)間復(fù)雜度 O(N2)O(N^2)O(N
2
) 會(huì)超時(shí)。必須想辦法優(yōu)化。

我們注意到，暴力解法中，如果數(shù)組的前半部分是單調(diào)不增的，那么會(huì)有很大的計(jì)算資源的浪費(fèi)。比如說(shuō) [6,5,4,3,8]，對(duì)于前面的 [6,5,4,3] 等數(shù)字都需要向后遍歷，當(dāng)尋找到元素 8 時(shí)才找到了比自己大的元素；而如果已知元素 6 向后找到元素 8 才找到了比自己的大的數(shù)字，那么對(duì)于元素 [5,4,3] 來(lái)說(shuō)，它們都比元素 6 更小，所以比它們更大的元素一定是元素 8，不需要單獨(dú)遍歷對(duì) [5,4,3] 向后遍歷一次！

根據(jù)上面的分析可知，可以遍歷一次數(shù)組，如果元素是單調(diào)遞減的（則他們的「下一個(gè)更大元素」相同），我們就把這些元素保存，直到找到一個(gè)較大的元素；把該較大元素逐一跟保存了的元素比較，如果該元素更大，那么它就是前面元素的「下一個(gè)更大元素」。

在實(shí)現(xiàn)上，我們可以使用「單調(diào)?！箒?lái)實(shí)現(xiàn)，單調(diào)棧是說(shuō)棧里面的元素從棧底到棧頂是單調(diào)遞增或者單調(diào)遞減的（類(lèi)似于漢諾塔）。

本題應(yīng)該用個(gè)「單調(diào)遞減?！箒?lái)實(shí)現(xiàn)。

建立「單調(diào)遞減?！?#xff0c;并對(duì)原數(shù)組遍歷一次：

如果棧為空，則把當(dāng)前元素放入棧內(nèi)；
如果棧不為空，則需要判斷當(dāng)前元素和棧頂元素的大小：
如果當(dāng)前元素比棧頂元素大：說(shuō)明當(dāng)前元素是前面一些元素的「下一個(gè)更大元素」，則逐個(gè)彈出棧頂元素，直到當(dāng)前元素比棧頂元素小為止。
如果當(dāng)前元素比棧頂元素小：說(shuō)明當(dāng)前元素的「下一個(gè)更大元素」與棧頂元素相同，則把當(dāng)前元素入棧。

注意：由于我們要找每一個(gè)元素的下一個(gè)更大的值，因此我們需要對(duì)原數(shù)組遍歷兩次，對(duì)遍歷下標(biāo)進(jìn)行取余轉(zhuǎn)換。

以及因?yàn)闂?nèi)存放的是還沒(méi)更新答案的下標(biāo)，可能會(huì)有位置會(huì)一直留在棧內(nèi)（最大值的位置），因此我們要在處理前預(yù)設(shè)答案為 -1。而從實(shí)現(xiàn)那些沒(méi)有下一個(gè)更大元素（不出棧）的位置的答案是 -1。

代碼：

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int>res(nums.size(),-1);stack<int>st;int n=nums.size();for(int i=0;i<2*n;i++){while(!st.empty()&&nums[st.top()]<nums[i%n]){res[st.top()]=nums[i%n];st.pop();}st.push(i%n);}return res;}
};

時(shí)間復(fù)雜度: O(n)，其中 n 是序列的長(zhǎng)度。我們需要遍歷該數(shù)組中每個(gè)元素最多 2 次，每個(gè)元素出棧與入棧的總次數(shù)也不超過(guò) 4 次。

空間復(fù)雜度: O(n，其中 n 是序列的長(zhǎng)度。空間復(fù)雜度主要取決于棧的大小，棧的大小至多為 2n?1。

36. 456 132模式

解法一：貪心+暴力求解【超時(shí)】

這個(gè)方法就是 O(N2)的解法，是這個(gè)題的暴力解法。

我選擇的方法是維護(hù) 132模式 中間的那個(gè)數(shù)字 3，因?yàn)?3 在 132 的中間的數(shù)字、也是最大的數(shù)字。我們的思路是個(gè)貪心的方法：我們要維護(hù)的 1 是 3 左邊的最小的數(shù)字； 2 是 3 右邊的比 3 小并且比 1 大的數(shù)字。

從左到右遍歷一次，遍歷的數(shù)字是 nums[j] 也就是 132 模式中的 3。根據(jù)上面的貪心思想分析，我們想讓 1 是 3 左邊最小的元素，然后使用暴力nums[j+1…N?1] 中找到 132 模式中的 2 就行。

這種做法會(huì)超時(shí)

解法二：單調(diào)棧

我們從后往前做，維護(hù)一個(gè)「單調(diào)遞減」的棧，同時(shí)使用 knum 記錄所有出棧元素的最大值（次大值）。

那么當(dāng)我們遍歷到 i，只要滿足發(fā)現(xiàn)滿足 nums[i] < knum ，說(shuō)明我們找到了符合條件的 i j k。

舉例子，對(duì)于樣例數(shù)據(jù) [3, 1, 4, 2]，我們知道滿足 132 結(jié)構(gòu)的子序列是 [1, 4, 2]，其處理邏輯是（遍歷從后往前）：

枚舉到 2：棧內(nèi)元素為 [2]，k = INF
枚舉到 4：不滿足「單調(diào)遞減」，2 出棧更新 knum ，4 入棧。棧內(nèi)元素為 [4]， knum = 2
枚舉到 1：滿足 nums[i] < knum ，說(shuō)明對(duì)于 i 而言，后面有一個(gè)比其大的元素（滿足 num[i]< knum 的條件），同時(shí)這個(gè) knum 的來(lái)源又是因?yàn)榫S護(hù)「單調(diào)遞減」而彈出導(dǎo)致被更新的（滿足 knum，有比 k 要大的元素，并且knum的索引位置大于此元素的索引位置）。因此我們找到了滿足 132 結(jié)構(gòu)的組合。

這樣做的本質(zhì)是：我們通過(guò)維護(hù)「單調(diào)遞減」來(lái)確保已經(jīng)找到了有效的 (jnum,knum)。換句話說(shuō)如果 knum有值的話，那么必然是因?yàn)橛?jnum > knum，導(dǎo)致的有值。也就是 132 結(jié)構(gòu)中，我們找到了 32，剩下的 i （也就是 132 結(jié)構(gòu)中的 1）則是通過(guò)遍歷過(guò)程中與 knum的比較來(lái)找到。這樣做的復(fù)雜度是 O(n 的，比樹(shù)狀數(shù)組還要快。

代碼：

class Solution {
public:bool find132pattern(vector<int>& nums) {stack<int>st;int n=nums.size();int knum=INT_MIN;for(int i=n-1;i>=0;i--){if(nums[i]<knum){return true;}while(!st.empty()&&st.top()<nums[i]){knum=max(knum,st.top());st.pop();}st.push(nums[i]);}return false;}};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

37. 316 去除重復(fù)字母

解法：貪心+單調(diào)棧

注意題目要求：1.要去重，2.不能打亂字符的相對(duì)順序 3.需要返回去重后字典序最小的結(jié)果

貪心的做法就是保證每一步的字符都是最小的，其可以使用【單調(diào)?！縼?lái)解決，只不過(guò)需要添加額外的數(shù)據(jù)結(jié)構(gòu)用于記錄字符的個(gè)數(shù)以及是否在棧中

• 遍歷一遍字符串，使用wordNum記錄每個(gè)字符的出現(xiàn)個(gè)數(shù)
• 利用isInstack初始化所有的字符都不在棧中，為0
• 此時(shí)我們從左到右遍歷字符串，每遍歷一個(gè)字符c，該字符出現(xiàn)的次數(shù)減一，即wordNum[c]-1;
  • 判斷如果c已經(jīng)在棧中，則跳過(guò)；
  • 否則就判斷c和當(dāng)前棧頂?shù)淖址鹴誰(shuí)大，假如c比t小，并且t此時(shí)的出現(xiàn)次數(shù)>0,那么將棧頂元素彈出，將c作為棧頂元素能讓字典序降低；所以我們對(duì)于棧中比c小并且出現(xiàn)次數(shù)大于0的字符全都彈出，并設(shè)置標(biāo)識(shí)為isInstack為false;
  • 最后將c加入棧中，并設(shè)置標(biāo)識(shí)為isInstack為true;
  • 最后我們返回的結(jié)果的逆序就是最終結(jié)果

代碼：

class Solution {
public:string removeDuplicateLetters(string s) {unordered_map<int,int>wordNum;vector<int>isInstack(256,0);for(auto c:s){wordNum[c]++;}stack<char>st;for(int i=0;i<s.size();i++){char c=s[i];wordNum[c]--;if(isInstack[c]){continue;}while(!st.empty()&&c<st.top()){if(wordNum[st.top()]>0){isInstack[st.top()]=0;st.pop();}else{break;}}st.push(c);isInstack[st.top()]=1;}string res="";while(!st.empty()){res+=st.top();st.pop();}reverse(res.begin(),res.end());return res;}
};

時(shí)間復(fù)雜度：O(N)，其中 N 為字符串長(zhǎng)度。代碼中雖然有雙重循環(huán)，但是每個(gè)字符至多只會(huì)入棧、出棧各一次。

空間復(fù)雜度：$O(|\Sigma |)$，其中 Σ為字符集合，本題中字符均為小寫(xiě)字母，所以 ∣Σ∣=26|。由于棧中的字符不能重復(fù)，因此棧中最多只能有 ∣Σ∣|個(gè)字符，另外需要維護(hù)兩個(gè)數(shù)組，分別記錄每個(gè)字符是否出現(xiàn)在棧中以及每個(gè)字符的剩余數(shù)量。

38. 402 移掉k位數(shù)字

解法：單調(diào)棧+貪心

對(duì)于兩個(gè)相同長(zhǎng)度的數(shù)字序列，最左邊不同的數(shù)字決定了這兩個(gè)數(shù)字的大小，例如，對(duì)于 A=1axxx，B=1bxxx，如果 a>b 則 A>B。

基于此，我們可以知道，若要使得剩下的數(shù)字最小，需要保證靠前的數(shù)字盡可能小。

讓我們從一個(gè)簡(jiǎn)單的例子開(kāi)始。給定一個(gè)數(shù)字序列，例如 425，如果要求我們只刪除一個(gè)數(shù)字，那么從左到右，我們有 4、2和 5 三個(gè)選擇。我們將每一個(gè)數(shù)字和它的左鄰居進(jìn)行比較。從 2 開(kāi)始，2 小于它的左鄰居 4。假設(shè)我們保留數(shù)字 4，那么所有可能的組合都是以數(shù)字 4（即 42、4）開(kāi)頭的。相反，如果移掉 4，留下 2，我們得到的是以 2 開(kāi)頭的組合（即 25），這明顯小于任何留下數(shù)字 4的組合。因此我們應(yīng)該移掉數(shù)字 4。如果不移掉數(shù)字 4，則之后無(wú)論移掉什么數(shù)字，都不會(huì)得到最小數(shù)。

基于上述分析，我們可以得出「刪除一個(gè)數(shù)字」的貪心策略：給定一個(gè)長(zhǎng)度為 n的數(shù)字序列$[D_0{D}_1{D}_2{D}_3\dots D_{n?1}]$，從左往右找到第一個(gè)位置 i（i>0）使得$D_i<D_{i?1}$，并刪去$D_{i?1}$；如果不存在，說(shuō)明整個(gè)數(shù)字序列單調(diào)不降，刪去最后一個(gè)數(shù)字即可。

思路：

考慮從左往右增量的構(gòu)造最后的答案。我們可以用一個(gè)棧維護(hù)當(dāng)前的答案序列，棧中的元素代表截止到當(dāng)前位置，刪除不超過(guò) k 次個(gè)數(shù)字后，所能得到的最小整數(shù)。根據(jù)之前的討論：在使用 k 個(gè)刪除次數(shù)之前，棧中的序列從棧底到棧頂單調(diào)不降。

因此，對(duì)于每個(gè)數(shù)字，如果該數(shù)字小于棧頂元素，我們就不斷地彈出棧頂元素，直到

• 棧為空
• 或者新的棧頂元素不大于當(dāng)前數(shù)字
• 或者我們已經(jīng)刪除了 k 位數(shù)字

代碼實(shí)現(xiàn)中注意的細(xì)節(jié)：

如果我們刪除了 cnt 個(gè)數(shù)字且 cnt<k，這種情況下我們需要從序列尾部刪除額外的 k?m 個(gè)數(shù)字,可以簡(jiǎn)單的將最后得到的stk截取前n-k個(gè)即可。
如果最終的數(shù)字序列存在前導(dǎo)零，我們要?jiǎng)h去前導(dǎo)零。
如果最終數(shù)字序列為空，我們應(yīng)該返回 0

代碼：

class Solution {
public:string removeKdigits(string num, int k) {int n=num.size();if(n==k){return "0";}string stk;int cnt=0;for(int i=0;i<n;i++){char c=num[i];if(cnt==k){   stk.push_back(c);continue;  }   while(!stk.empty()&&stk.back()>c){stk.pop_back();cnt++;if(cnt==k)break;}stk.push_back(c);}stk=stk.size()==n-k?stk:stk.substr(0,n-k);  string ans="";bool isFirstDigit=false;for(char c:stk){if(c!='0'){isFirstDigit=true;}if(isFirstDigit)ans+=c;}return ans==""?"0":ans;}
};

時(shí)間復(fù)雜度：O(n)，其中 n 為字符串的長(zhǎng)度。盡管存在嵌套循環(huán)，但內(nèi)部循環(huán)最多運(yùn)行 k 次。由于0<k≤n，主循環(huán)的時(shí)間復(fù)雜度被限制在 2n2n 以內(nèi)。對(duì)于主循環(huán)之外的邏輯，它們的時(shí)間復(fù)雜度是 O(n)，因此總時(shí)間復(fù)雜度為O(n)。

空間復(fù)雜度：O(n)。棧存儲(chǔ)數(shù)字需要線性的空間。

39. 321 拼接最大數(shù)

解法：單調(diào)棧+分治

和402移掉k位數(shù)字類(lèi)似，只不不過(guò)這一次是兩個(gè)數(shù)組，而不是一個(gè)，并且是求最大數(shù)。

最大最小是無(wú)關(guān)緊要的，關(guān)鍵在于是兩個(gè)數(shù)組，并且要求從兩個(gè)數(shù)組選取的元素個(gè)數(shù)加起來(lái)一共是 k。

然而在一個(gè)數(shù)組中取 k 個(gè)數(shù)字，并保持其最小（或者最大），我們已經(jīng)會(huì)了。但是如果問(wèn)題擴(kuò)展到兩個(gè)，會(huì)有什么變化呢？

實(shí)際上，問(wèn)題本質(zhì)并沒(méi)有發(fā)生變化。 假設(shè)我們從 nums1 中取了 k1 個(gè)，從 num2 中取了 k2 個(gè)，其中 k1 + k2 = k。而 k1 和 k2 這 兩個(gè)子問(wèn)題我們是會(huì)解決的。由于這兩個(gè)子問(wèn)題是相互獨(dú)立的，因此我們只需要分別求解，然后將結(jié)果合并即可。

假如 k1 和 k2 個(gè)數(shù)字，已經(jīng)取出來(lái)了。那么剩下要做的就是將這個(gè)長(zhǎng)度分別為 k1 和 k2 的數(shù)字，合并成一個(gè)長(zhǎng)度為 k 的數(shù)組合并成一個(gè)最大的數(shù)組。

以題目的 nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 為例。 假如我們從 num1 中取出 1 個(gè)數(shù)字，那么就要從 nums2 中取出 4 個(gè)數(shù)字。

運(yùn)用第一題的方法，我們計(jì)算出應(yīng)該取 nums1 的 [6]，并取 nums2 的 [9,5,8,3]。 如何將 [6] 和 [9,5,8,3]，使得數(shù)字盡可能大，并且保持相對(duì)位置不變呢？

實(shí)際上這個(gè)過(guò)程有點(diǎn)類(lèi)似歸并排序中的治，而上面我們分別計(jì)算 num1 和 num2 的最大數(shù)的過(guò)程類(lèi)似歸并排序中的分。

• 我們將從 num1 中挑選的 k1 個(gè)數(shù)組成的數(shù)組稱之為 A，將從 num2 中挑選的 k2 個(gè)數(shù)組成的數(shù)組稱之為 B。這里需要說(shuō)明一下。 在很多編程語(yǔ)言中：如果 A 和 B 是兩個(gè)數(shù)組，當(dāng)前僅當(dāng) A 的首個(gè)元素字典序大于 B 的首個(gè)元素，A > B 返回 true，否則返回 false。

具體算法：

從 nums1 中 取 min(i,len(nums1)) 個(gè)數(shù)形成新的數(shù)組 A（取的邏輯同第一題），其中 i 等于 0,1,2, … k。
從 nums2 中 對(duì)應(yīng)取 min(j,len(nums2)) 個(gè)數(shù)形成新的數(shù)組 B（取的邏輯同第一題），其中 j 等于 k - i。
注意我這里取數(shù)的上限，即不能超過(guò)數(shù)組本身的長(zhǎng)度，這點(diǎn)容易大家忽略

將 A 和 B 按照上面的 merge 方法合并
上面我們暴力了 k 種組合情況，我們只需要將 k 種情況取出最大值即可。

代碼細(xì)節(jié)：需要注意的是，兩個(gè)數(shù)組合并的過(guò)程中，使用雙指針itrA和itrB，如果碰到數(shù)字相同的時(shí)候，需要比較后續(xù)的數(shù)字，直到數(shù)字不同，才能決定加入A中的數(shù)字還是B中的數(shù)字。

C++中編寫(xiě)了自定義compare函數(shù)進(jìn)行比較，主要就是從A的itrA和B的itrB開(kāi)始，利用A[itrA]-B[itrB]來(lái)比較兩個(gè)的大小，A和B都是vector,A[itrA]-B[itrB]計(jì)算的就是字典序的差值，如果相同則循環(huán)比較后面的字符

代碼：

class Solution {
public:vector<int>pick_max(vector<int>&nums,int k){vector<int>res;int cnt=nums.size()-k;for(int i=0;i<nums.size();i++){while(cnt&&!res.empty()&&res.back()<nums[i]){res.pop_back();cnt--;}res.push_back(nums[i]);}res.resize(k);return res;}int compare(vector<int>& A, int itrA, vector<int>& B, int itrB) {int x = A.size(), y = B.size();while (itrA < x && itrB < y) {int difference = A[itrA] - B[itrB];if (difference != 0) {return difference;}itrA++;itrB++;}return (x - itrA) - (y - itrB);}vector<int> merge(vector<int>&A,vector<int>&B){int len=A.size()+B.size();vector<int>ans(len);int itrA=0,itrB=0;for(int i=0;i<len;i++){if(compare(A,itrA,B,itrB)>0){ans[i]=A[itrA++];}else{ans[i]=B[itrB++];}}return ans;}vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {vector<int>res(k,0);for(int i=0;i<=k;i++){if(i<=nums1.size()&&(k-i)<=nums2.size()){vector<int>sub1=pick_max(nums1,i);vector<int>sub2=pick_max(nums2,k-i);vector<int>cur_res=merge(sub1,sub2);if(cur_res>res)res.swap(cur_res);}}return res;}
};

時(shí)間復(fù)雜度：pick_max 的時(shí)間復(fù)雜度為 O(M+N)，其中 M 為 nums1 的長(zhǎng)度，N 為 nums2 的長(zhǎng)度。 merge 的時(shí)間復(fù)雜度為 O(k)，再加上外層遍歷所有的 k 中可能性。因此總的時(shí)間復(fù)雜度為 O(k2?(M+N)。
空間復(fù)雜度：我們使用了額外的 stack 和 ans 數(shù)組，因此空間復(fù)雜度為 O(max(M,N,k))，其中 M 為 nums1 的長(zhǎng)度，N 為 nums2 的長(zhǎng)度。

40. 84 柱狀圖中最大的矩形

解法一：單調(diào)棧+哨兵【減少邊界判斷】

單調(diào)棧分為單調(diào)遞增棧和單調(diào)遞減棧

1.單調(diào)遞增棧即棧內(nèi)元素保持單調(diào)遞增的棧

同理單調(diào)遞減棧即棧內(nèi)元素保持單調(diào)遞減的棧
操作規(guī)則（下面都以單調(diào)遞增棧為例）

2，如果新的元素比棧頂元素大，就入棧

如果新的元素較小，那就一直把棧內(nèi)元素彈出來(lái)，直到棧頂比新元素小
加入這樣一個(gè)規(guī)則之后，會(huì)有什么效果

3.棧內(nèi)的元素是遞增的

當(dāng)元素出棧時(shí)，說(shuō)明這個(gè)新元素是出棧元素向后找第一個(gè)比其小的元素
舉個(gè)例子，配合下圖，現(xiàn)在索引在 6 ，棧里是 1 5 6 。
接下來(lái)新元素是 2 ，那么 6 需要出棧。
當(dāng) 6 出棧時(shí)，右邊 2 代表是 6 右邊第一個(gè)比 6 小的元素。

當(dāng)元素出棧后，說(shuō)明新棧頂元素是出棧元素向前找第一個(gè)比其小的元素
當(dāng) 6 出棧時(shí)，5 成為新的棧頂，那么 5 就是 6 左邊第一個(gè)比 6 小的元素。

那么就確定了6為矩形高度的最大面積，即夾在5和2索引之間的寬度，即left=1+1【5的索引+1】，right=3-1【右邊的索引減1】

寬度w=right-left+1=2-2+1,面積為6*1=6

因此思路為：

1. 對(duì)于一個(gè)高度，如果能得到向左和向右的邊界
2. 那么就能對(duì)每個(gè)高度求一次面積
3. 遍歷所有高度，即可得出最大面積
4. 使用單調(diào)棧，在出棧操作時(shí)得到前后邊界并計(jì)算面積

注意增加了哨兵機(jī)制 ：

彈棧的時(shí)候，棧為空；
遍歷完成以后，棧中還有元素；
為此可以我們可以在輸入數(shù)組的兩端加上兩個(gè)高度為 0 （或者是 0.5，只要比 1 嚴(yán)格小都行）的柱形，可以回避上面這兩種分類(lèi)討論。

這兩個(gè)站在兩邊的柱形有一個(gè)很形象的名詞，叫做哨兵（Sentinel）。

有了這兩個(gè)柱形：

左邊的柱形（第 1 個(gè)柱形）由于它一定比輸入數(shù)組里任何一個(gè)元素小，它肯定不會(huì)出棧，因此棧一定不會(huì)為空；

右邊的柱形（第 2 個(gè)柱形）也正是因?yàn)樗欢ū容斎霐?shù)組里任何一個(gè)元素小，它會(huì)讓所有輸入數(shù)組里的元素出棧（第 1 個(gè)哨兵元素除外）。

這里棧對(duì)應(yīng)到高度，呈單調(diào)增加不減的形態(tài)，因此稱為單調(diào)棧（Monotone Stack）。它是暴力解法的優(yōu)化，計(jì)算每個(gè)柱形的高度對(duì)應(yīng)的最大矩形的順序由出棧順序決定。

代碼：

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int ans=0;vector<int>st;heights.insert(heights.begin(),0);heights.push_back(0);for(int i=0;i<heights.size();i++){while(!st.empty()&&heights[st.back()]>heights[i]){int cur=st.back();st.pop_back();int left=st.back()+1;int right=i-1;ans=max(ans,(right-left+1)*heights[cur]);}st.push_back(i);}return ans;}
};

• 時(shí)間復(fù)雜度：O(N)。
• 空間復(fù)雜度：O(N)。

41. 85 最大矩形

解法：

前綴和 + 單調(diào)棧
為了方便，我們令 matrix 為 mat，記矩陣的行高為 n，矩陣的列寬為 m。

定義坐標(biāo)系 : 左上角坐標(biāo)為 (1,1)，右下角坐標(biāo)為 (n,m)。

我們將 mat 的每一行作為基準(zhǔn)，以基準(zhǔn)線為起點(diǎn)，往上連續(xù) 1 的個(gè)數(shù)為高度。

以題目樣例進(jìn)行說(shuō)明：

紅框部分代表「以第一行作為基準(zhǔn)線，統(tǒng)計(jì)每一列中基準(zhǔn)線及以上連續(xù) 111 的個(gè)數(shù)」，此時(shí)只有第一行，可得：[1,0,1,0,0]
黃框部分代表「以第二行作為基準(zhǔn)線，統(tǒng)計(jì)每一列中基準(zhǔn)線及以上連續(xù) 111 的個(gè)數(shù)」，此時(shí)有第一行和第二行，可得：[2,0,2,1,1]
藍(lán)框部分代表「以第三行作為基準(zhǔn)線，統(tǒng)計(jì)每一列中基準(zhǔn)線及以上連續(xù) 111 的個(gè)數(shù)」，此時(shí)有三行，可得：[3,1,3,2,2]
…
將原矩陣進(jìn)行這樣的轉(zhuǎn)換好處是 : 對(duì)于原矩中面積最大的矩形，其下邊緣必然對(duì)應(yīng)了某一條基準(zhǔn)線，從而將問(wèn)題轉(zhuǎn)換為（題解）84. 柱狀圖中最大的矩形 。

預(yù)處理基準(zhǔn)線數(shù)據(jù)可以通過(guò)前綴和思想來(lái)做，構(gòu)建一個(gè)二維數(shù)組 sum（為了方便，我們令二維數(shù)組下標(biāo)從 1 開(kāi)始）并從上往下地構(gòu)造：

$sum[i][j]=\{\begin{array}{ll}0& mat[i][j]=0\\ sum[i?1][j]+1& mat[i][j]=1\end{array}$

當(dāng)有了 sum 之后，則是和 （題解）84. 柱狀圖中最大的矩形 一樣的做法 : 枚舉高度 + 單調(diào)棧,直接調(diào)用84題函數(shù)。

代碼：

class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {int n=matrix.size(),m=matrix[0].size(),ans=0;vector<vector<int>>sum(n+10,vector<int>(m+10,0));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){sum[i][j]=matrix[i-1][j-1]=='0'?0:sum[i-1][j]+1;}}for(int i=1;i<=n;i++){vector<int>&heights=sum[i];ans=max(ans,largestRectangleArea(heights));}return ans;}int largestRectangleArea(vector<int>& heights) {int ans=0;vector<int>st;heights.insert(heights.begin(),0);heights.push_back(0);for(int i=0;i<heights.size();i++){while(!st.empty()&&heights[st.back()]>heights[i]){int cur=st.back();st.pop_back();int left=st.back()+1;int right=i-1;ans=max(ans,(right-left+1)*heights[cur]);}st.push_back(i);}return ans;}
};

• 時(shí)間復(fù)雜度：O(n×m）
• 空間復(fù)雜度：O(n×m)