LeetCode热题100(25.10.22)

一：接雨水

1. 动态规划

使用两个数组维护其左右最大高度，其当前位置的雨水即为左右高度的最小值减去当前值

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        int result = 0;
        vector<int> LeftH(len);
        vector<int> rightH(len);
        LeftH[0] = height[0];
        rightH[len - 1] = height[len - 1];
        for (int i = 1; i < len; ++i)
            LeftH[i] = max(LeftH[i - 1], height[i]);
        for (int i = len - 2; i >= 0; --i)
            rightH[i] = max(rightH[i + 1], height[i]);
        for (int i = 0; i < len; ++i)
            result += min(LeftH[i], rightH[i]) - height[i];
        return result;
    }
};

2. 单调栈

按照递减的顺序将数据放入栈中，如果有数据大于栈顶，则计算其包含的雨水量

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        int result = 0;
        stack<int> stk;
        for (int i = 0; i < len; ++i)
        {
            while (!stk.empty() && height[i] > height[stk.top()])
            {
                int cur = stk.top();
                stk.pop();
                if (stk.empty()) break;
                int left = stk.top();
                int width = i - left - 1;
                int hei = min(height[left], height[i]) - height[cur];
                result += width * hei;
            }
            stk.push(i);
        }
        return result;
    }
};

3. 双指针

使用两个指针维护左右的最大值，哪个指针的值小便进行移动

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        int result = 0;
        int left = 0, right = len - 1;
        int leftM = 0, rightM = 0;
        while (left < right)
        {
            leftM = max(leftM, height[left]);
            rightM = max(rightM, height[right]);
            if (leftM < rightM)
            {
                result += leftM - height[left];
                ++left;
            } else
            {
                result += rightM - height[right];
                --right;
            }
        }
        return result;
    }
};

二：滑动窗口最大值

1. 优先队列

维护一个当前窗口的优先队列，每次从里面选中一个最大值作为当前窗口的最大值，然后移动窗口并剔除超出边界的队顶元素

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < k; ++i) pq.push({nums[i], i});
        result.emplace_back(pq.top().first);
        for (int i = k; i < nums.size(); ++i)
        {
            pq.push({nums[i], i});
            while (pq.top().second <= i - k) pq.pop();
            result.emplace_back(pq.top().first);
        }
        return result;
    }
};

2. 单调队列

将优先队列改为双端队列，同时维护有序状态，可将原来操作插入的$\log(n)$复杂度降低为$(n)$

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq;
        for (int i = 0; i < k; ++i)
        {
            while (!dq.empty() && nums[i] >= nums[dq.back()]) dq.pop_back();
            dq.push_back(i);
        }
        result.emplace_back(nums[dq.front()]);
        for (int i = k; i < nums.size(); ++i)
        {
            while (!dq.empty() && nums[i] >= nums[dq.back()]) dq.pop_back();
            dq.push_back(i);
            while (dq.front() <= i - k) dq.pop_front();
            result.emplace_back(nums[dq.front()]);
        }
        return result;
    }
};

3. 分块+预处理

首先将元素分块，并计算出当前元素在该块的前缀最大值和后缀最大值，随后遍历元素取其中的最大值即可

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size();
        vector<int> result;
        vector<int> pre(len);
        vector<int> suf(len);
        for (int i = 0; i < len; ++i)
            if (i % k == 0)
                pre[i] = nums[i];
            else
                pre[i] = max(pre[i - 1], nums[i]);
        for (int i = len - 1; i >= 0; --i)
            if (i == len - 1 || (i + 1) % k == 0)
                suf[i] = nums[i];
            else
                suf[i] = max(suf[i + 1], nums[i]);
        for (int i = 0; i <= len - k; ++i)
            result.emplace_back(max(pre[i + k - 1], suf[i]));
        return result;
    }
};

三：最小覆盖子串

1. 滑动窗口

使用一个窗口来表示当前子串的范围，并在包含所有元素之后尝试缩短长度

class Solution {
public:
    unordered_map <char, int> ori, cnt;
    string minWindow(string s, string t) {
        for (const auto &c: t)
            ++ori[c];
        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1;
        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) 
                ++cnt[s[r]];
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l; // 记录最短子串的起始位置
                }
                if (ori.find(s[l]) != ori.end()) 
                    --cnt[s[l]];
                ++l;
            }
        }
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
    bool check() 
    {
        for (const auto &p: ori) 
            if (cnt[p.first] < p.second) 
                return false;
        return true;
    }
};