文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個(gè)數(shù)組 arr ，該數(shù)組表示一個(gè)從 1 到 n 的數(shù)字排列。有一個(gè)長度為 n 的二進(jìn)制字符串，該字符串上的所有位最初都設(shè)置為 0 。

在從 1 到 n 的每個(gè)步驟 i 中（假設(shè)二進(jìn)制字符串和 arr 都是從 1 開始索引的情況下），二進(jìn)制字符串上位于位置 arr[i] 的位將會(huì)設(shè)為 1 。

給你一個(gè)整數(shù) m ，請(qǐng)你找出二進(jìn)制字符串上存在長度為 m 的一組 1 的最后步驟。一組 1 是一個(gè)連續(xù)的、由 1 組成的子串，且左右兩邊不再有可以延伸的 1 。

返回存在長度 恰好 為 m 的 一組 1 的最后步驟。如果不存在這樣的步驟，請(qǐng)返回 -1 。

示例 1： 輸入：arr = [3,5,1,2,4], m = 1 輸出：4 解釋： 步驟 1："00100"，由 1 構(gòu)成的組：["1"] 步驟 2："00101"，由 1 構(gòu)成的組：["1", "1"] 步驟 3："10101"，由 1 構(gòu)成的組：["1", "1", "1"] 步驟 4："11101"，由 1 構(gòu)成的組：["111", "1"] 步驟 5："11111"，由 1 構(gòu)成的組：["11111"] 存在長度為 1 的一組 1 的最后步驟是步驟 4 。示例 2： 輸入：arr = [3,1,5,4,2], m = 2 輸出：-1 解釋： 步驟 1："00100"，由 1 構(gòu)成的組：["1"] 步驟 2："10100"，由 1 構(gòu)成的組：["1", "1"] 步驟 3："10101"，由 1 構(gòu)成的組：["1", "1", "1"] 步驟 4："10111"，由 1 構(gòu)成的組：["1", "111"] 步驟 5："11111"，由 1 構(gòu)成的組：["11111"] 不管是哪一步驟都無法形成長度為 2 的一組 1 。示例 3： 輸入：arr = [1], m = 1 輸出：1示例 4： 輸入：arr = [2,1], m = 2 輸出：2提示： n == arr.length 1 <= n <= 10^5 1 <= arr[i] <= n arr 中的所有整數(shù) 互不相同 1 <= m <= arr.length

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-latest-group-of-size-m
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

class Solution { public:int findLatestStep(vector<int>& arr, int m) {int n = arr.size(), i, ans = -1;vector<vector<int>> pos(n+2, vector<int>(2, -1));//存儲(chǔ)該組的左右端點(diǎn)位置vector<int> len(n+1, 0);//長度為x的有多少組int l1,r1,l2,r2,n1,n2,nall,l,r;for(i = 0; i < n; ++i){l = r = arr[i];nall = 1;n1 = n2 = 0;if(pos[l-1][0] != -1)//左邊存在{l1 = pos[l-1][0];r1 = pos[l-1][1];n1 = r1-l1+1;}if(pos[l+1][0] != -1)//右邊存在{l2 = pos[l+1][0];r2 = pos[l+1][1];n2 = r2-l2+1;}if(n1){l = min(l, l1);nall += n1;len[n1]--;}if(n2){r = max(r, r2);nall += n2;len[n2]--;}len[nall]++;pos[l][0] = l;pos[l][1] = r;pos[r][0] = l;pos[r][1] = r;if(len[m])ans = i+1;}return ans;} };

648 ms 127.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1562. 查找大小为 M 的最新分组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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