題目

題目大意

有 N + 1 個水龍頭分別在 0 ~ N 的位置，給你一個陣列，每個水龍頭打開後可以淋到的範圍，例如 [3,4,1,1,0,0] 中第一個 3 代表可以淋到 -3 ~ 3，0 代表這個水龍頭不能開。
問至少要開幾個水龍頭，可以使 0 ~ N 每個位置都被淋到。

想法

直覺是 O(n log n) 的 sort 後掃一遍，但這樣的解法不值得 hard 這個難度，所以要想想看有沒有 O(n) 的做法。
可能會想到 L 和 R 各維護一個遞增的 stack，但下一個 L 會被上一個 R 影響，顯然需要兩個一起維護，所以就 stack< pair<int, int> > 啦XD
應該有想到 stack 這題就解掉了，但要注意一個細節：可能 stack 裡面的 range 會變成 (0, 5) (1, 6) (2, 7)，回傳 3，實際上卻只需要 (0, 5) 和 (2, 7)，但各種 push 和 pop 好像沒辦法判斷掉(有人想到的話可以跟我說，因為我想不到)，只能從存的值去改善，所以就想到：乾脆讓放進去的 L 是最後一段的 R 就好啦！這樣 (1, 6) 會變成 (5, 6)，(2, 7) 完全覆蓋掉他了，所以 size = 2。
寫著寫著發現好像這裡在一開始就應該能想到的，可能太疏忽了QQ

Code(C++)

int minTaps(int n, vector<int>& ranges) {
    stack< pair<int, int> >s;
    for(int i=0; i<=n; i++) {
        if (!ranges[i]) continue;
        int L = max(0, i - ranges[i]), R = min(n, i + ranges[i]);
        if (s.empty()) {
            s.push({L, R});
            continue;
        } else if (R <= s.top().second) continue;
        while(!s.empty() && s.top().first >= L) s.pop();
        if (!s.empty()) L = max(L, s.top().second);
        s.push({L, R});
    }
    int last = n + 1, ans = s.size();
    while(!s.empty()) {
        pair<int, int> x = s.top();
        s.pop();
        if (x.second + 1 < last) return -1;
        last = x.first;
    }
    return last > 0 ? -1 : ans;
}

心得

一開始沒注意到 0 是不能開，因為題目說 [i - ranges[i], i + ranges[i]] ...，還好範測第二筆有。
送出後發現還沒特別優化，時間和空間就拿到 80% 跟 85%，覺得心情很好XD