雙周賽 57 題解

知識點：優先隊列，差分數組，單調棧

四道題都不難，中間兩題卡了我比較長時間，幸虧最後一題是個單調棧一眼題，不然就要掉大分了

檢查是否所有字元出現次數相同

給定一個字元串 \(s\)，如果 \(s\) 中所有字元串出現的次數一樣，那麼我們稱之為好字元串，請傳回 \(s\) 是否是好字元串

題解

把每一個字元出現的次數用桶維護，扔到集合裡面去，利用集合的去重功能，判斷集合的

size

是否為 \(1\)

class Solution {
public:
    bool areOccurrencesEqual(string s) {
        vector<int> a(26);
        int n = s.length();
        set<int> st;
        for (int i = 0; i < n; ++i) a[s[i] - 'a']++;
        for (int i = 0; i < 26; ++i)
            if (a[i]) st.insert(a[i]);
        return st.size() == 1;
    }
};
           

最小未被占據椅子的編号

\(n\) 個人在辦聚會，有無限個椅子，每個人有到達時間和離開時間，每個人到達聚會的時候會選擇空閑的最小編号的椅子

現在給定 \(n\) 個人的到達時間和離開時間，計算出第 \(t\) 個人坐的椅子的編号

用一個優先隊列存儲每個椅子的空閑時間和編号，用一個集合存儲 \(n\) 個椅子的編号

周遊 \(n\) 個人，根據到達時間和離開時間處理空閑和忙碌的椅子，更新優先隊列和集合即可

// cpp
struct node {
    int idx, ed;
    node() {}
    node(int _idx, int _ed):
        idx(_idx), ed(_ed) {}
};
bool operator< (const node& x, const node& y) {
    if (x.ed == y.ed) return x.idx < y.idx;
    return x.ed > y.ed;
}

bool cmp(vector<int> &x, vector<int> &y) {
    if (x[0] == y[0]) return x[1] < y[1];
    return x[0] < y[0];
}
class Solution {
public:
    int smallestChair(vector<vector<int>>& t, int target) {
        vector<int> vec;
        int n = t.size();
        for (int i = 0; i < n; ++i) vec.push_back(i), t[i].push_back(i);
        set<int> st(vec.begin(), vec.end());
        priority_queue<node> pq;
        sort(t.begin(), t.end(), cmp);
        int res = 0;
        for (int i = 0; i < n; ++i) {
            while (!pq.empty()) {
                node temp = pq.top();
                if (temp.ed <= t[i][0]) pq.pop(), st.insert(temp.idx);
                else break;
            }
            res = *st.begin();
            pq.push(node(res, t[i][1]));
            st.erase(st.begin());
            if (t[i][2] == target) break;
        }
        return res;
    }
};
           

描述繪畫結果

給定 \(n\) 個左閉右開區間 \([l,\ r)\)，并給這個區間上每一個值加上 \(w\)

傳回操作後的數軸，要求将相同值寫成左閉右開區間的形式，值為 \(0\) 的區間跳過

舉例來講，如果 \(1,\ 2,\ 3\) 的值都是 \(12\)，并且 \(4\) 的值為 \(13\)，那我們可以把其合并成 \([1,\ 4),\ [4,\ 5)\)，

注意，對于值相同的區間，如果達到這個和的方式不一樣，不能寫成一個區間

例如 \([1, 4),\ [4,\ 7)\) 均為 \(12\)，但前者為 \(5 + 7\)，後者為 \(3 + 9\)，此時我們不能将其合并

原題題意比較備援，也很難抽象題意描述，但是考點很簡單：差分數組

差分數組說的是：做 \(n\) 次區間加法操作，可以用離線算法在 \(O(n)\) 時間得到更新後的區間

具體來講，如果要給區間 \([l,\ r)\) 統一加上 \(w\)，隻需要在 \(l\) 處加上 \(w\)，在 \(r\) 處減去 \(w\)，如此進行 \(n\) 次，最後對原數組進行字首和，便可以得到更新後的數組，這裡的「原數組」被稱為差分數組

我們對更新後的數組進行劃分，将相同的值歸納為一個區間即可

此題在差分數組的基礎上多了一個要求：對于值相同的區間，如果達到這個和的方式不一樣，不能寫成一個區間

這個也比較好處理，利用貪心的思想，繼續構造一個差分數組，區間加「區間右端點」的值即可，聰明的你能想明白貪心的正确性嗎？

時間複雜度 \(O(n)\)

// cpp
typedef long long LL;
class Solution {
public:
    vector<vector<long long>> splitPainting(vector<vector<int>>& seg) {
        int n = seg.size();
        int maxx = 0;
        for (int i = 0; i < n; ++i) {
            maxx = max(maxx, seg[i][1]);
            seg[i].push_back(i + 1);
        }
        vector<LL> vec1(maxx + 7);
        vector<LL> vec2(maxx + 7);
        for (int i = 0; i < n; ++i) {
            int a = seg[i][0], b = seg[i][1], c = seg[i][2], d = seg[i][3];
            vec1[a] += c, vec1[b] -= c;
            vec2[a] += d, vec2[b] -= d;
        }
        for (int i = 1; i <= maxx; ++i) {
            vec1[i] += vec1[i - 1];
            vec2[i] += vec2[i - 1];
        }
        vector<vector<LL>> ans;
        int a = 1, b = 1;
        for (int i = 1; i <= maxx; ++i) {
            if (vec1[i] != vec1[a] || vec1[i] == vec1[a] && vec2[i] != vec2[a]) {
                if (!vec1[i - 1]) {a = b = i; continue;}
                else {
                    ans.push_back(vector<LL>{a, i, vec1[i - 1]});
                    a = b = i;
                }
            }
        }
        return ans;
    }
};
           

從隊列中可以看到的人數

給定 \(n\) 個人及其身高 \(h_{i}\)

對于兩個人 \(i,\ j\)，其中 \(i\) 在 \(j\) 左邊，如果 \(i,\ j\) 中間的每一個人都沒有他們高，那麼 \(i\) 可以看到右邊的 \(j\)

計算出每個人可以看到的右邊的人數

資料規定

\(1\leq n\leq 10^5\)

對于目前的 \(i\) 而言，我們可以計算出他左邊第一個比他高的人 \(L\)，以及右邊第一個比他高的人 \(R\)

// cpp
class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& h) {
        int n = h.size();
        vector<int> rmax(n + 7);
        vector<int> lmax(n + 7);
        vector<int> ans(n + 7);
        vector<int> a(n + 7);
        for (int i = 1; i <= n; ++i) a[i] = h[i - 1];
        stack<int> mono1, mono2; // 遞增
        for (int i = 1; i <= n; ++i) {
            while (!mono1.empty() && a[mono1.top()] < a[i]) {
                rmax[mono1.top()] = i;
                mono1.pop();
            }
            mono1.push(i);
        }
        for (int i = n; i >= 1; --i) {
            while (!mono2.empty() && a[mono2.top()] < a[i]) {
                lmax[mono2.top()] = i;
                mono2.pop();
            }
            mono2.push(i);
        }
        for (int i = 1; i <= n; ++i) {
            int L = lmax[i], R = rmax[i];
            if (L >= 1 && L <= n) ans[L]++;
            if (R >= 1 && R <= n) ans[i]++;
        }
        return {ans.begin() + 1, ans.begin() + 1 + n};
    }
};