Leetcode第138次周赛解题报告

速度AK了，遇到会的知识点猛如狗

1051. 高度检查器

知识点：模拟
效率：$O(nlogn)$，即排序效率，可通过桶排降低为$O(n)$
根据题意：

1. 将原数组排序
2. 比较当前数组与原数组不一样的下标个数

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        vector<int> origin = heights;
        sort(heights.begin(),heights.end());
        int cnt = 0;
        int len = origin.size();
        for(int i = 0;i < len;i++) cnt += (origin[i]!=heights[i]);
        return cnt;
    }
};

1052. 爱生气的书店老板

知识点：滑动窗口
效率：$O(n)$
维护一个滑动窗口，统计滑动窗口内的每个下标i，当grumpy[i] == 1时customers[i]之和，找到此值最大的滑动窗口。
找到最大的滑动窗口后，与遍历滑动窗口过程中顺带统计的grumpy[i] == 0时customers[i]之和相加，得到答案

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int len = customers.size();
        int sum1 = 0;
        int sum0 = 0;
        int minNumsum = 0;
        for(int i = 0;i < len;i++) {
            if(grumpy[i] == 1) sum1 += customers[i];
            else sum0 += customers[i];
            if(i-minutes >= 0 && grumpy[i-minutes] == 1) sum1 -= customers[i-minutes];
            minNumsum = max(sum1,minNumsum);
        }
        return sum0+minNumsum;
    }
};

1053. 交换一次的先前排列

知识点：逆序对
效率：$O(n)$，一次倒序遍历，一次正序遍历，一次交换
归纳：假定给一个序列的值V，本题的目标是寻找一个出现的逆序对(Vi,Vj)满足:Vi>Vj && i<j，该逆序对满足如下特征：

• 没有更大的i or j

也就是说，找最后一个出现的逆序数对，进行交换。假如找不见逆序数对，则返回数组本身

寻找最大逆序数对：

1. 倒叙遍历，维护当前最小值数组：$O(n)$。
2. 顺序遍历，假如最小值数组minNums[i]小于当前数，说明后面有比当前数更小的数，即存在逆序对，更新逆序对的左值：$O(n)$
3. 根据找到的最大左值，寻找逆序对右值，并进行交换：$O(n+1)$

因此 实现了$O(n)$复杂度

这道题一开始写了一个$O(n^2)$复杂度的 结果超时了

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        int len = arr.size();
        bool flag = false;
        vector<int> minNums(len,999999);
        for(int i = len-2;i >= 0;i--) {
            if(arr[i+1] <= minNums[i+1]) minNums[i] = arr[i+1];
            else minNums[i] = minNums[i+1];
        }
        int idx = -1;
        for(int i = 0;i < len;i++) {
            if(minNums[i] < arr[i]) idx = i;
        }
        if(idx==-1) return arr;
        int mx = -1;
        int mxidx = -1;
        for(int i = idx + 1;i < len;i++) 
            if(arr[i] > mx && arr[i] < arr[idx])
                mx = arr[i],mxidx = i;
        swap(arr[idx],arr[mxidx]);
        return arr;
    }
};

1054. 距离相等的条形码

知识点：堆/优先队列
效率：$O(nlogn)$
解题过程：

1. 统计每个数字的出现次数，按出现次数进行排序：构建堆$O(n)$
2. 每次取出出现次数Top1和Top2的数，即取一对出现次数最多的数，放到答案中：调整两次堆 $O(2*log2n)$
3. 然后分别更新出现次数，进行-1，再放回到排序的堆中，更新一次堆形成新的顺序：调整两次堆 $O(2*log2n)$

为什么使用堆？因为堆通常是小规模TopK问题的解法，尤其在动态维护的场景下，能够获得相对于完全重新排序的较低时间复杂度。一个问题中假如只需要取头部固定个数目的元素，而且排序顺序是动态更新的，那么一般再用堆。

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        vector<int> ans;
        unordered_map <int,int> mp;
        priority_queue <pair<int,int>> p;
        for(auto i:barcodes) mp[i]++;
        for(auto [a,b]:mp) p.push({b,a});
        while(!p.empty()) {
            auto x = p.top();
            p.pop();
            if(p.empty()) {
                ans.push_back(x.second);
                x.first--;
            }else{
                auto y = p.top();
                p.pop();
                ans.push_back(x.second);
                x.first--;
                ans.push_back(y.second);
                y.first--;
                if(y.first > 0) p.push(y);
                    
            }
            if(x.first > 0) p.push(x);
        }
        return ans;
    }
};