說明：貪心的本質(zhì)是選擇每一階段的局部最優(yōu)，從而達(dá)到全局最優(yōu)。
1 簡單貪心
// 455. 分發(fā)餅干
// 假設(shè)你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。
// 局部最優(yōu)就是大餅干喂給胃口大的，充分利用餅干尺寸喂飽一個，全局最優(yōu)就是喂飽盡可能多的小孩。
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int start = s.length - 1;
for (int i = g.length - 1; i >=0; i--) {
if (start >= 0 && s[start] >= g[i]) {
start--;
count++;
}
}
return count;
}
}
// 1005. K 次取反后最大化的數(shù)組和
// 給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，按以下方法修改該數(shù)組：選擇某個下標(biāo) i 并將 nums[i] 替換為 -nums[i] 。重復(fù)這個過程恰好 k 次。可以多次選擇同一個下標(biāo) i 。以這種方式修改數(shù)組后，返回?cái)?shù)組 可能的最大和 。
// 1局部最優(yōu)：讓絕對值大的負(fù)數(shù)變?yōu)檎龜?shù)，當(dāng)前數(shù)值達(dá)到最大，整體最優(yōu)：整個數(shù)組和達(dá)到最大。
// 2局部最優(yōu)：只找數(shù)值最小的正整數(shù)進(jìn)行反轉(zhuǎn)，當(dāng)前數(shù)值可以達(dá)到最大.全局最優(yōu)：整個數(shù)組和 達(dá)到最大。
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Integer[] arr = Arrays.stream(nums).boxed().toArray(size->new Integer[size]);
Arrays.sort(arr,(p1,p2)->Integer.compare(Math.abs(p1),Math.abs(p2)));
nums = Arrays.stream(arr).mapToInt(i->i).toArray();
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] < 0 && k > 0) {
nums[i] = -nums[i];
k--;
}
}
if (k != 0) nums[0] = k % 2 == 1 ? -nums[0] : nums[0];
return Arrays.stream(nums).sum();
}
}
// 860. 檸檬水找零
// 在檸檬水?dāng)偵?，每一杯檸檬水的售價為 5 美元。顧客排隊(duì)購買你的產(chǎn)品，（按賬單 bills 支付的順序）一次購買一杯。每位顧客只買一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。注意，一開始你手頭沒有任何零錢。給你一個整數(shù)數(shù)組 bills ，其中 bills[i] 是第 i 位顧客付的賬。如果你能給每位顧客正確找零，返回 true ，否則返回 false 。
// 情況一：賬單是5，直接收下。
// 情況二：賬單是10，消耗一個5，增加一個10
// 情況三：賬單是20，優(yōu)先消耗一個10和一個5，如果不夠，再消耗三個5
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0,ten = 0,twenty = 0;
for (int bill : bills) {
if (bill == 5) five++;
if (bill == 10) {
if (five <= 0) return false;
ten++;
five--;
}
if (bill == 20) {
if (ten > 0 && five > 0) {
twenty++;
ten--;
five--;
} else if (five >= 3) {
twenty++;
five -= 3;
} else {
return false;
}
}
}
return true;
}
}
2 序列問題
// 376. 擺動序列
// 如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替，則數(shù)字序列稱為 擺動序列 。第一個差（如果存在的話）可能是正數(shù)或負(fù)數(shù)。僅有一個元素或者含兩個不等元素的序列也視作擺動序列。例如， [1, 7, 4, 9, 2, 5] 是一個 擺動序列 ，因?yàn)椴钪?(6, -3, 5, -7, 3) 是正負(fù)交替出現(xiàn)的。相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是擺動序列，第一個序列是因?yàn)樗那皟蓚€差值都是正數(shù)，第二個序列是因?yàn)樗淖詈笠粋€差值為零。子序列 可以通過從原始序列中刪除一些（也可以不刪除）元素來獲得，剩下的元素保持其原始順序。給你一個整數(shù)數(shù)組 nums ，返回 nums 中作為 擺動序列 的 最長子序列的長度 。
// 局部最優(yōu)：刪除單調(diào)坡度上的節(jié)點(diǎn)（不包括單調(diào)坡度兩端的節(jié)點(diǎn)），那么這個坡度就可以有兩個局部峰值。整體最優(yōu)：整個序列有最多的局部峰值，從而達(dá)到最長擺動序列。實(shí)際操作上，其實(shí)連刪除的操作都不用做，因?yàn)轭}目要求的是最長擺動子序列的長度，所以只需要統(tǒng)計(jì)數(shù)組的峰值數(shù)量就可以了（相當(dāng)于是刪除單一坡度上的節(jié)點(diǎn)，然后統(tǒng)計(jì)長度）
// 統(tǒng)計(jì)峰值的時候，數(shù)組最左面和最右面是最不好統(tǒng)計(jì)的。例如序列[2,5]，它的峰值數(shù)量是2，如果靠統(tǒng)計(jì)差值來計(jì)算峰值個數(shù)就需要考慮數(shù)組最左面和最右面的特殊情況。所以可以針對序列[2,5]，可以假設(shè)為[2,2,5]，這樣它就有坡度了即preDiff = 0。針對以上情形，result初始為1（默認(rèn)最右面有一個峰值），此時curDiff > 0 && preDiff <= 0，那么result++（計(jì)算了左面的峰值），最后得到的result就是2（峰值個數(shù)為2即擺動序列長度為2）
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) return nums.length;
int preDiff = 0;
int curDiff = 0;
int count = 1;
for (int i = 1; i < nums.length; i++) {
curDiff = nums[i] - nums[i - 1];
if (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
count++;
preDiff = curDiff;
}
}
return count;
}
}
// 738. 單調(diào)遞增的數(shù)字
// 給定一個非負(fù)整數(shù) N，找出小于或等于 N 的最大的整數(shù)，同時這個整數(shù)需要滿足其各個位數(shù)上的數(shù)字是單調(diào)遞增。（當(dāng)且僅當(dāng)每個相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時，我們稱這個整數(shù)是單調(diào)遞增的。）
// 局部最優(yōu)：遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]--，然后strNum[i]給為9，可以保證這兩位變成最大單調(diào)遞增整數(shù)。全局最優(yōu)：得到小于等于N的最大單調(diào)遞增的整數(shù)。
class Solution {
public int monotoneIncreasingDigits(int n) {
String[] strs = (n + "").split("");
int start = strs.length;
for (int i = strs.length - 1; i > 0; i--) {
if (Integer.valueOf(strs[i]) < Integer.valueOf(strs[i - 1])) {
strs[i - 1] = (Integer.valueOf(strs[i - 1]) - 1) + "";
start = i;
}
}
for (int i = start; i < strs.length; i++) {
strs[i] = "9";
}
return Integer.valueOf(String.join("",strs));
}
}
3 股票問題
// 122. 買賣股票的最佳時機(jī) II
// 給定一個數(shù)組 prices ，其中 prices[i] 是一支給定股票第 i 天的價格。設(shè)計(jì)一個算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
// 局部最優(yōu)：收集每天的正利潤，全局最優(yōu)：求得最大利潤。把利潤分解為每天為單位的維度。
class Solution {
public int maxProfit(int[] prices) {
int sum = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] - prices[i - 1] > 0) {
sum += prices[i] - prices[i - 1];
}
}
return sum;
}
}
// 714. 買賣股票的最佳時機(jī)含手續(xù)費(fèi)
// 給定一個整數(shù)數(shù)組 prices，其中第 i 個元素代表了第 i 天的股票價格 ；整數(shù) fee 代表了交易股票的手續(xù)費(fèi)用。你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購買了一個股票，在賣出它之前你就不能再繼續(xù)購買股票了。返回獲得利潤的最大值。注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續(xù)費(fèi)。
// 如果使用貪心策略，就是最低值買，最高值（如果算上手續(xù)費(fèi)還盈利）就賣。
// 情況一：收獲利潤的這一天并不是收獲利潤區(qū)間里的最后一天（不是真正的賣出，相當(dāng)于持有股票），所以后面要繼續(xù)收獲利潤。
// 情況二：前一天是收獲利潤區(qū)間里的最后一天（相當(dāng)于真正的賣出了），今天要重新記錄最小價格了。
// 情況三：不作操作，保持原有狀態(tài)（買入，賣出，不買不賣）
class Solution {
public int maxProfit(int[] prices, int fee) {
int buy = prices[0] + fee;
int res = 0;
for (int price : prices) {
if (price + fee < buy) {
buy = price + fee;
} else if (price > buy) {
res += price - buy;
buy = price; //后面要繼續(xù)收獲利潤,已經(jīng)扣除了fee
}
}
return res;
}
}
4 兩個維度權(quán)衡問題
// 135. 分發(fā)糖果
// n 個孩子站成一排。給你一個整數(shù)數(shù)組 ratings 表示每個孩子的評分。你需要按照以下要求，給這些孩子分發(fā)糖果：每個孩子至少分配到 1 個糖果。相鄰兩個孩子評分更高的孩子會獲得更多的糖果。請你給每個孩子分發(fā)糖果，計(jì)算并返回需要準(zhǔn)備的 最少糖果數(shù)目 。
// 一定是要確定一邊之后，再確定另一邊，例如比較每一個孩子的左邊，然后再比較右邊，如果兩邊一起考慮一定會顧此失彼。
// 先確定右邊評分大于左邊的情況（也就是從前向后遍歷）此時局部最優(yōu)：只要右邊評分比左邊大，右邊的孩子就多一個糖果，全局最優(yōu)：相鄰的孩子中，評分高的右孩子獲得比左邊孩子更多的糖果
// 再確定左孩子大于右孩子的情況（從后向前遍歷）。因?yàn)槿绻麖那跋蚝蟊闅v，根據(jù) ratings[i + 1] 來確定 ratings[i] 對應(yīng)的糖果，那么每次都不能利用上前一次的比較結(jié)果
class Solution {
public int candy(int[] ratings) {
int[] candyVec = new int[ratings.length];
candyVec[0] = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candyVec[i] = candyVec[i - 1] + 1;
} else {
candyVec[i] = 1;
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyVec[i] = Math.max(candyVec[i],candyVec[i + 1] + 1);
}
}
int sum = 0;
for (int candy : candyVec) {
sum += candy;
}
return sum;
}
}
// 406. 根據(jù)身高重建隊(duì)列
// 假設(shè)有打亂順序的一群人站成一個隊(duì)列，數(shù)組 people 表示隊(duì)列中一些人的屬性（不一定按順序）。每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi ，前面 正好 有 ki 個身高大于或等于 hi 的人。請你重新構(gòu)造并返回輸入數(shù)組 people 所表示的隊(duì)列。返回的隊(duì)列應(yīng)該格式化為數(shù)組 queue ，其中 queue[j] = [hj, kj] 是隊(duì)列中第 j 個人的屬性（queue[0] 是排在隊(duì)列前面的人）。
// 局部最優(yōu)：優(yōu)先按身高高的people的k來插入。插入操作過后的people滿足隊(duì)列屬性。全局最優(yōu)：最后都做完插入操作，整個隊(duì)列滿足題目隊(duì)列屬性。
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(num1,num2) -> {
if (num1[0] == num2[0]) {
return num1[1] - num2[1];
} else {
return num2[0] - num1[0];
}
});
List<int[]> list = new LinkedList<>();
for (int[] p : people) {
list.add(p[1],p);
}
return list.toArray(new int[people.length][]);
}
}
5 區(qū)間問題
// 55. 跳躍游戲
// 給定一個非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個下標(biāo) 。數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達(dá)最后一個下標(biāo)。
// 貪心算法局部最優(yōu)解：每次取最大跳躍步數(shù)（取最大覆蓋范圍），整體最優(yōu)解：最后得到整體最大覆蓋范圍，看是否能到終點(diǎn)。
class Solution {
public boolean canJump(int[] nums) {
int cover = 0;
if (nums.length == 1) return true;
for (int i = 0; i <= cover; i++) {
cover = Math.max(cover,i + nums[i]);
if (cover >= nums.length - 1) return true;
}
return false;
}
}
// 45. 跳躍游戲 II
// 給你一個非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的第一個位置。數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個位置。假設(shè)你總是可以到達(dá)數(shù)組的最后一個位置。
// 從覆蓋范圍出發(fā)，不管怎么跳，覆蓋范圍內(nèi)一定是可以跳到的，以最小的步數(shù)增加覆蓋范圍，覆蓋范圍一旦覆蓋了終點(diǎn)，得到的就是最小步數(shù)。這里需要統(tǒng)計(jì)兩個覆蓋范圍，當(dāng)前這一步的最大覆蓋和下一步最大覆蓋。
class Solution {
public int jump(int[] nums) {
if (nums.length == 1) return 0;
int ans = 0;
int curDistance = 0, nextDistance = 0;
for (int i = 0; i < nums.length; i++) {
nextDistance = Math.max(nextDistance,i + nums[i]);
if (i == curDistance) {
ans++;
curDistance = nextDistance;
if (curDistance >= nums.length - 1) break;
}
}
return ans;
}
}
// 452. 用最少數(shù)量的箭引爆氣球
// 在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結(jié)束坐標(biāo)。由于它是水平的，所以縱坐標(biāo)并不重要，因此只要知道開始和結(jié)束的橫坐標(biāo)就足夠了。開始坐標(biāo)總是小于結(jié)束坐標(biāo)。一支弓箭可以沿著 x 軸從不同點(diǎn)完全垂直地射出。在坐標(biāo) x 處射出一支箭，若有一個氣球的直徑的開始和結(jié)束坐標(biāo)為 xstart，xend， 且滿足 xstart ≤ x ≤ xend，則該氣球會被引爆?？梢陨涑龅墓臄?shù)量沒有限制。 弓箭一旦被射出之后，可以無限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。給你一個數(shù)組 points ，其中 points [i] = [xstart,xend] ，返回引爆所有氣球所必須射出的最小弓箭數(shù)。
// 局部最優(yōu)：當(dāng)氣球出現(xiàn)重疊，一起射，所用弓箭最少。全局最優(yōu)：把所有氣球射爆所用弓箭最少。
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points,(p1,p2)->{
if (p1[0] != p2[0]) {
return Integer.compare(p1[0],p2[0]);
} else {
return Integer.compare(p1[1],p2[1]);
}
});
int count = 1;
int[] tmp = new int[]{points[0][0],points[0][1]};
for (int i = 1; i < points.length; i++) {
if (tmp[1] >= points[i][0]) {
tmp[1] = Math.min(tmp[1],points[i][1]);
} else {
count++;
tmp = new int[] {points[i][0],points[i][1]};
}
}
return count;
}
}
// 435. 無重疊區(qū)間
// 給定一個區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。注意:可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。
// 按照右邊界排序，就要從左向右遍歷，因?yàn)橛疫吔缭叫≡胶茫灰疫吔缭叫?，留給下一個區(qū)間的空間就越大，所以從左向右遍歷，優(yōu)先選右邊界小的。按照右邊界排序，從左向右記錄非交叉區(qū)間的個數(shù)。最后用區(qū)間總數(shù)減去非交叉區(qū)間的個數(shù)就是需要移除的區(qū)間個數(shù)了。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length < 2) return 0;
Arrays.sort(intervals,(p1,p2)->{
if (p1[1] != p2[1]) {
return Integer.compare(p1[1],p2[1]);
} else {
return Integer.compare(p1[0],p2[0]);
}
});
int[] tmp = new int[] {intervals[0][0],intervals[0][1]};
int validAns = 1;
for (int i = 1; i < intervals.length; i++) {
if (tmp[1] > intervals[i][0]) continue;
validAns++;
tmp = new int[] {intervals[i][0],intervals[i][1]};
}
return intervals.length - validAns;
}
}
// 763. 劃分字母區(qū)間
// 字符串 S 由小寫字母組成。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現(xiàn)在一個片段中。返回一個表示每個字符串片段的長度的列表。
// 在遍歷的過程中相當(dāng)于是要找每一個字母的邊界，如果找到之前遍歷過的所有字母的最遠(yuǎn)邊界，說明這個邊界就是分割點(diǎn)了。此時前面出現(xiàn)過所有字母，最遠(yuǎn)也就到這個邊界了。
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<>();
int[] hash = new int[26];
for (int i = 0; i < s.length(); i++) {
hash[s.charAt(i) - 'a'] = i;
}
int curIndex = 0;
int preIndex = -1;
for (int i = 0; i < s.length(); i++) {
curIndex = Math.max(curIndex,hash[s.charAt(i) - 'a']);
if (i == curIndex) {
res.add(curIndex - preIndex);
curIndex = 0;
preIndex = i;
}
}
return res;
}
}
// 56. 合并區(qū)間
// 以數(shù)組 intervals 表示若干個區(qū)間的集合，其中單個區(qū)間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區(qū)間，并返回一個不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間。
// 按照左邊界排序，排序之后局部最優(yōu)：每次合并都取最大的右邊界，這樣就可以合并更多的區(qū)間了，整體最優(yōu)：合并所有重疊的區(qū)間。
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
Arrays.sort(intervals,(o1,o2) -> {
return Integer.compare(o1[0],o2[0]);
});
int start = intervals[0][0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] > intervals[i - 1][1]) {
res.add(new int[]{start,intervals[i - 1][1]});
start = intervals[i][0];
} else {
intervals[i][1] = Math.max(intervals[i][1],intervals[i - 1][1]);
}
}
res.add(new int[]{start,intervals[intervals.length - 1][1]});
return res.toArray(new int[res.size()][]);
}
}
6 其他問題
// 53. 最大子數(shù)組和
// 給你一個整數(shù)數(shù)組 nums ，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。子數(shù)組 是數(shù)組中的一個連續(xù)部分。
// 局部最優(yōu)：當(dāng)前“連續(xù)和”為負(fù)數(shù)的時候立刻放棄，從下一個元素重新計(jì)算“連續(xù)和”，因?yàn)樨?fù)數(shù)加上下一個元素 “連續(xù)和”只會越來越小。全局最優(yōu)：選取最大“連續(xù)和”
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1) return nums[0];
int sum = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++) {
count += nums[i];
sum = Math.max(sum,count);
if (count < 0) count = 0;
}
return sum;
}
}
// 134. 加油站
// 在一條環(huán)路上有 N 個加油站，其中第 i 個加油站有汽油 gas[i] 升。你有一輛油箱容量無限的的汽車，從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升。你從其中的一個加油站出發(fā)，開始時油箱為空。如果你可以繞環(huán)路行駛一周，則返回出發(fā)時加油站的編號，否則返回 -1。說明: 如果題目有解，該答案即為唯一答案。輸入數(shù)組均為非空數(shù)組，且長度相同。輸入數(shù)組中的元素均為非負(fù)數(shù)。
// 局部最優(yōu)：當(dāng)前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因?yàn)閺膉開始一定不行。全局最優(yōu)：找到可以跑一圈的起始位置。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) {
start = i + 1; // 更新起點(diǎn) -> 局部最優(yōu)
curSum = 0;
}
}
return totalSum < 0 ? -1 : start; // 如果總的油量小于總油耗量，說明怎么走都不符合。
}
}
// 968. 監(jiān)控二叉樹
// 給定一個二叉樹，我們在樹的節(jié)點(diǎn)上安裝攝像頭。節(jié)點(diǎn)上的每個攝影頭都可以監(jiān)視其父對象、自身及其直接子對象。計(jì)算監(jiān)控樹的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量。
// 情況1：左右節(jié)點(diǎn)都有覆蓋
// 情況2：左右節(jié)點(diǎn)至少有一個無覆蓋的情況
// 情況3：左右節(jié)點(diǎn)至少有一個有攝像頭
// 情況4：頭結(jié)點(diǎn)沒有覆蓋
class Solution {
// 0: 未覆蓋，1:攝像頭，2:已覆蓋
private int res = 0;
public int minCameraCover(TreeNode root) {
if (traversal(root) == 0) {
res++;
}
return res;
}
private int traversal(TreeNode root) {
if (root == null) return 2;
int left = traversal(root.left);
int right = traversal(root.right);
if (left == 2 && right == 2) return 0;
if (left == 0 || right == 0) {
res++;
return 1;
}
if (left == 1 || right == 1) {
return 2;
}
return -1;
}
}
