寫(xiě)在前面

上個(gè)周末的周賽題，自己寫(xiě)的時(shí)候就使用隊(duì)列和遞歸模擬嘗試了一下，時(shí)間復(fù)雜度O(n2)，不過(guò)超時(shí)了。自己平時(shí)對(duì)數(shù)據(jù)規(guī)模與復(fù)雜度的關(guān)系也不是很清楚，都是靠直覺(jué)，在想辦法優(yōu)化的時(shí)候犯了難，想要優(yōu)化到O(n)，但是沒(méi)想出來(lái)合適的解決辦法，只能放棄。這里先記錄一下正常情況下算法的時(shí)間復(fù)雜度與數(shù)據(jù)規(guī)模之間的關(guān)系。借用Santan's Death兄弟的博客

題目

核心思路

雖然題目很長(zhǎng)而且有點(diǎn)晦澀難懂，不過(guò)只要按照題目給的示例自己模擬一遍就很容易理解題目的意思了，我就不在過(guò)多解釋了。

直觀模擬

直接暴力思想破解的話(huà)就是模擬他的過(guò)程，維護(hù)一個(gè)字符數(shù)組(初始狀態(tài)全部填 '0')，然后根據(jù) arr 數(shù)組的值依次更新數(shù)組中指定位置的字符，并且計(jì)算該步驟是否滿(mǎn)足存在長(zhǎng)度恰好為m的一組1(稱(chēng)為一次好操作)，遍歷完成后最后一次好操作就是答案。
既然題目想要尋找的是最后一次好操作，那么我們可以逆序遍歷，也就是相當(dāng)于一串 '1' 按照 arr 數(shù)組的順序變更為一串 '0'，此時(shí)只要找到第一次好操作返回即可。不過(guò)逆序遍歷的平均復(fù)雜度并沒(méi)有得到優(yōu)化，若不存在好操作，還是會(huì)遍歷所有的結(jié)果，所以核心的優(yōu)化并不在這里。
而通過(guò)數(shù)據(jù)規(guī)模10^5可以知道算法的時(shí)間復(fù)雜度應(yīng)該在 O(nlogn) 左右，而常見(jiàn)的優(yōu)化方法就是二分查找，這道題給的標(biāo)簽也恰好是二分查找。由于逆序遍歷的時(shí)候，每次循環(huán)只會(huì)更新一個(gè)先前存儲(chǔ)過(guò)的區(qū)間 (假如原有一個(gè)子串'1111'，對(duì)應(yīng)存儲(chǔ)0 和 3，若接下來(lái)的步驟更新下標(biāo)2，變?yōu)?code>'1101'，在區(qū)間中插入一個(gè)1，更新為0 1 3) ，所以使用二分查找找到這個(gè)區(qū)間是可行的，不過(guò)我太菜了，沒(méi)寫(xiě)出來(lái)。。。選擇了使用一個(gè)TreeSet，從而滿(mǎn)足查找的時(shí)間復(fù)雜度為 O(nlogn)。

模擬法代碼

class Solution {
    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        if (m == n)
            return n;

        TreeSet<Integer> set = new TreeSet<Integer>();
        // 相當(dāng)于在最后一步驟形成的1串的左右各加一個(gè)0
        set.add(0);
        set.add(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            int index = arr[i];
            int low = set.lower(index);
            int high = set.higher(index);

            if (high - index - 1 == m || index - low - 1 == m) {
                return i;
            }
            set.add(index);
        }
        return -1;
    }
}

在最開(kāi)始，現(xiàn)在set中加入 0 和 n + 1，這樣可以保證操作一致，因?yàn)閮蛇吺?code>0和一邊是0、另一邊是1的情況計(jì)算連續(xù)1串長(zhǎng)度的方法是不一樣的，所以相當(dāng)于在串的兩端各補(bǔ)了一個(gè)0。然后使用TreeSet中的lower()方法和higher()方法獲取需要更新的區(qū)間的兩端，然后判斷、更新即可，代碼比較簡(jiǎn)單，不過(guò)耗時(shí)350ms比較久。

類(lèi)似鏈表的解法

由于求解的是每一個(gè)連續(xù)的'1'串長(zhǎng)度，所以實(shí)際有用的下標(biāo)就是首和尾，然后我們每次插入一個(gè)'1'的時(shí)候更新一下首尾指針，保證每一個(gè)'1'串開(kāi)頭位置的右指針指向結(jié)尾、結(jié)尾位置的左指針指向開(kāi)頭，并且維護(hù)一個(gè)cnt記錄長(zhǎng)度為m的'1'串的個(gè)數(shù)，每次操作都分別更新cnt變量，如果一次操作后cnt的值大于0，則代表這是一次好操作，然后保存最后一次好操作即可。

圖解

• 插入位置左右兩邊都是0
• 插入位置左右兩邊都是1
• 插入位置左邊是0右邊是1
• 插入位置左邊是1右邊是0
  我們定義兩個(gè)數(shù)組：l[i]表示i位置的左指針，r[i]表示i位置的右指針，并假設(shè)當(dāng)前位置為x
  雖然圖中例子只給了前兩種情況，不過(guò)后兩種情況與之類(lèi)似，可以對(duì)照著寫(xiě)出指針更新過(guò)程，另外，由于每個(gè)位置都要考慮左右兩邊的字符的情況，所以可以在開(kāi)頭與結(jié)尾分別加一個(gè)0，保證操作的一致性。
  首先考慮可能一：左右兩邊都是0，這時(shí)候只要將插入位置的左右指針都指向自己即可。所以此時(shí)的操作應(yīng)為：

  l[x] = r[x] = x

可能二：左右兩邊都是1(步驟四和步驟五的過(guò)程)，也就代表左邊和右邊均有'1'串，長(zhǎng)度可能是任意的，假設(shè)兩邊長(zhǎng)度都是1的情況(步驟四)，那么使左邊元素的右指針指向右邊元素，右邊元素的左指針指向左邊元素即可：

r[x - 1] = x + 1;
l[x + 1] = x - 1;

但是實(shí)際可能還有更長(zhǎng)的串(步驟五)，左邊長(zhǎng)度為3，右邊長(zhǎng)度為1，根據(jù)圖解，應(yīng)該將最左邊元素的右指針指向最右邊的元素，最右邊元素的左指針指向最左邊元素，而根據(jù)步驟四，最左邊元素可以通過(guò)x元素左邊元素的左指針獲得，同理最右邊元素也可以根據(jù)x位置右邊元素的右指針獲得，于是我們可以得到這樣的操作：

r[l[x - 1]] = r[x + 1];//l[x - 1]為左邊串的最左端元素
l[r[x + 1]] = l[x - 1];//r[x + 1]為右邊串的最右端元素

可能三與可能四與上邊可能類(lèi)似，就不再贅述了，還需要考慮的就是在更新左右指針的過(guò)程中怎么更新 cnt 變量。參考圖解

• 可能一：左右都是0時(shí)，只有m = 1是要執(zhí)行cnt++
• 可能二：左右都是1時(shí)，由于左右兩邊的串都有可能長(zhǎng)度為m，此時(shí)連接之前應(yīng)該將cnt--，而連接之后的串也可能出現(xiàn)長(zhǎng)度為m的'1'串，所以連接之后若滿(mǎn)足應(yīng)cnt++
• 可能三與可能四：類(lèi)似于可能二，分別考慮連接前串是否有長(zhǎng)度為m，連接之后是否出現(xiàn)長(zhǎng)度為m的串
  這樣我們?cè)谧钔鈱油ㄟ^(guò)一次循環(huán)遍歷arr數(shù)組，并對(duì)每個(gè)元素進(jìn)行更新左右指針數(shù)組，并且判斷本次是否為好操作即可。

完整代碼

class Solution {
    private int[] l, r;// 當(dāng)前位置的左右指針，0表示null

    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        if (m == n)
            return n;

        l = new int[n + 2];
        r = new int[n + 2];
        int res = -1, cnt = 0;
        for (int i = 0; i < n; i++) {
            int x = arr[i];
            if (r[x + 1] != 0 && l[x - 1] != 0) {
                if (len(l[x - 1]) == m)
                    cnt--;
                if (len(x + 1) == m)
                    cnt--;
                r[l[x - 1]] = r[x + 1];
                l[r[x + 1]] = l[x - 1];
                if (len(l[x - 1]) == m)
                    cnt++;
            } else if (l[x - 1] != 0) {
                if (len(l[x - 1]) == m)
                    cnt--;
                l[x] = l[x - 1];
                r[l[x - 1]] = x;
                if (len(l[x - 1]) == m)
                    cnt++;
            } else if (r[x + 1] != 0) {
                if (len(x + 1) == m)
                    cnt--;
                r[x] = r[x + 1];
                l[r[x + 1]] = x;
                if (len(x) == m)
                    cnt++;
            } else {
                l[x] = r[x] = x;
                if (m == 1)
                    cnt++;
            }

            if (cnt > 0)
                res = i + 1;
        }
        return res;
    }

    /**
     * 計(jì)算左端為left的1串的長(zhǎng)度
     * 
     * @param left
     * @return
     */
    public int len(int left) {
        return r[left] - left + 1;
    }
}

代碼顯得很長(zhǎng)，不過(guò)實(shí)際上只是四種情況的分類(lèi)討論，理解了圖解指針更新的過(guò)程，代碼還是比較好懂的。

總結(jié)

第一種方法直觀而且代碼簡(jiǎn)潔，靈活的使用了TreeSet，不過(guò)時(shí)間效率比較低；第二種方法雖然代碼也不是很長(zhǎng)，但是這種思想不是很好想到，不過(guò)O(n)的時(shí)間復(fù)雜度還是很快的。自己對(duì)于數(shù)據(jù)結(jié)構(gòu)的理解和運(yùn)用還是不夠熟練啊，另外這道題也讓我了解了數(shù)據(jù)規(guī)模與目標(biāo)算法時(shí)間復(fù)雜度的關(guān)系，收獲頗豐。
文章中若有不正確的地方還請(qǐng)指出，感恩相遇~~