thetheOrange的笔记

单调队列基本用法

发表于 2024-12-13 更新于 2024-12-20 分类于数组本文字数： 1k 阅读时长 ≈ 2 分钟

寻找各个子窗口的最大值

假如说，我们的目的是找到每一个子窗口的最大值。最简单的方法，是依次枚举所有的子窗口，
分别求出各个窗口的最大值。显然，这样的时间复杂度是O(n^2)的。其实，我们可以创建一个双端队列deque，
用于维护每个窗口的可能最大值。

这个队列满足一个条件，即小压大，换句话说，这个队列从队尾到队头，是严格单调递增的。

向右扩展窗口，即压入元素时，如果该元素破坏了队列的单调性，也就是说，该元素大于队尾元素，这时需要我们依次弹出小于该元素的队尾元素。
假如该元素大于队尾元素，为了找到最大值的可能性，显然，队尾元素应该弹出，让更大的元素进来。假如该元素等于队尾元素，虽然值相等，但是
该元素的坐标要更靠后，也就是说，窗口缩小的时候，该元素不容易被排除在外，更有成为最大值的可能。

向右缩小窗口，即弹出元素时，此时子窗口的最大值即为队列的头部元素。

因为每个元素都只进和出队列一次，所以时间复杂度为O(n)

例题

239. 滑动窗口最大值

给你一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

这道题就是经典的单调队列模版题，可以参考如下解法：

class Solution {
public:
    int deque[100001];
    int h, t;
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        h = 0, t = 0;
        int n = nums.size() - k + 1;
        vector<int> ans(n, 0);
        for (int r = 0, l = 0; r < nums.size(); ++r) {
            // push元素进入单调队列
            while (h < t && nums[r] >= nums[deque[t-1]]) {
                t--;
            }
            deque[t++] = r;
            // 满足条件则收集答案
            if (r - l + 1 == k) {
                ans[l] = nums[deque[h]];
                // 移动左指针，更新单调队列头部位置
                if (deque[h] == l) {
                    h++;
                }
                l++;
            }
        }
        return ans;
    }
};

适用场景

在一个一维数组中，对每个元素，寻找他的下一个或前一个最近的最大值或最小值的坐标或值。

若不考虑单调栈，采用暴力方法，对每个元素，分别向左向右遍历，找到第一个满足条件的元素就break，即可求解。暴力的方法的时间复杂度是O(n^2)。

单调栈维护一个单调递增或递减的栈，以寻找下一个最小值的坐标为例，即在栈里维护大压小的顺序。一般来说，使用单调栈右三个阶段：

遍历阶段。遍历每一个元素，满足条件则入栈，不满足大压小的条件则弹出栈顶元素，每次弹出，则结算栈顶元素的答案。此时，使栈顶元素弹出的元素为，该栈顶元素的右答案，栈顶元素的下一个栈中元素为左答案。
清算阶段。如果栈中有剩余元素，依次弹出，每个弹出的元素的右答案为-1，如果栈顶元素不是最后一个元素，则左答案为栈中下一个元素，否则，为-1。
修正阶段。如果数组中出现重复的元素，则需要修正答案。除最后一个元素外，倒序对每一个元素的右答案进行修正。如果nums[右答案]和元素的值相同，则修正该答案为ans[ans[i][1]][1]，即右答案的右答案。

因为每一个元素进出栈一次，所以时间复杂度为O(n)。

注意，单调栈维护的顺序和题目条件有关，例如，如果要找前一个或下一个最近的最大值坐标。则需要维护小压大的顺序。

算法模版

#define MAXN 1000001

static int nums[MAXN];
static int stack[MAXN];
static int ans[MAXN][2];
static int n, r;

void f() {
    r = 0;
    int cur;
    for (int i = 0; i < n; ++i) {
        // 当栈不为空且入栈元素大于栈顶元素时
        while (r > 0 && nums[stack[r-1]] >= nums[i]) {
            // 弹出该元素，结算答案
            cur = stack[--r];
            // 压在下面的元素为左答案，使其弹出的元素为右答案
            ans[cur][0] = r > 0 ? stack[r-1] : -1;
            ans[cur][1] = i;
        }
        stack[r++] = i;
    }
    // 如果栈中还有元素
    while (r > 0) {
        cur = stack[--r];
        // 此时右答案为-1 左答案为下一个元素
        ans[cur][0] = r > 0 ? stack[r-1] : -1;
        ans[cur][1] = -1;
    }
    // 修正答案 最后一个元素可以不考虑，因为都为-1
    for (int i = n - 2; i >= 0; --i) {
        if (ans[i][1] != -1 && nums[ans[i][1]] == nums[i]) {
            ans[i][1] = ans[ans[i][1]][1];
        }
    }
    // 输出
    for (int i = 0; i < n; ++i) {
        cout << ans[i][0] << ' ' << ans[i][1] << endl;
    }
}

例题分析

496. 下一个更大元素 I

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个比 x 大的元素。

给你两个没有重复元素的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的下一个更大元素。

对于nums2，可以先求出每一个元素的下一个最大元素的位置，然后我们对nums2的值和下标做一个映射，为了方便查找nums1中值对应的位置。

求出每一个元素的下一个最大元素位置的过程，可以考虑使用单调栈。

class Solution {
public:
    int stk[1001];
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums2.size(); ++i) {
            m[nums2[i]] = i;
        }
        int n1 = nums1.size();
        vector<int> ans(n1, -1);    
        int r = 0, n2 = nums2.size();
        vector<int> next(n2, -1);
        for (int i = 0; i < n2; ++i) {
            while (r > 0 && nums2[i] > nums2[stk[r-1]]) {
                int cur = stk[--r];
                next[cur] = nums2[i];
            }
            stk[r++] = i;
        }
        for (int i = 0; i < n1; ++i) {
            int pos = m[nums1[i]];
            ans[i] = next[pos];
        }
        return ans;
    }
};

一维差分总结

发表于 2024-11-29 分类于数组本文字数： 2.2k 阅读时长 ≈ 4 分钟

适用情景

如果要对数组的多个区间内的元素进行增减操作，可以考虑使用差分数组进行批量化操作。

思路

一般思路

差分数组实质上是前缀和数组的逆过程。

如果要对区间[l, r]内的元素加val，先求差分数组diff，diff数组大小为n+2, 可以避免讨论边界条件，其中diff数组内元素为原数组前后两个元素的差。接下来依次按如下过程操作：

diff[l+1] += val
diff[r+2] -= val

最后对整个差分数组进行求取前缀和，所得的数组即为修改后的数组。

例如，对数组nums = [2, 3, 4, 5]的[1, 3]区间内的所有元素+1，可以使用如下代码进行操作：

def f(nums: list[int], l: int, r: int) -> None:
    diff: list[int] = [0] * (len(nums) + 2)
    diff[1] = nums[0]
    # 求差分数组
    for i in range(1, len(nums)):
        diff[i + 1] = nums[i] - nums[i - 1]
    # 修改区间内的值
    diff[l + 1] += 1
    diff[r + 2] -= 1
    # 求前缀和
    for i in range(len(nums)):
        diff[i + 1] += diff[i]
        print(diff[i + 1], end=" ")

输出示例

2 4 5 6

等差数列的一维差分

这部分的思想是，对于某个区间内的元素，加上某个等差数列，例如，对某个区间[1, 2, 3, 4]，我们想让该区间的所有元素加上一个等差数列an = 1 + (n - 1) * 1 = n。换句话说，我们期待得到[1+1, 2+2, 3+3, 4+4]，即[2, 4, 6, 8]的结果。那么，我们可以从结果出发，进行推导。

为了简单，假设这样一个数组[0, 0, 0, 0, 0, 0, 0, 0]，设变量s为首项，d为公差，e为末项。[0, s, s+d, s+2d, s+3d, e, 0, 0]是我们的期望。

注意到，对[0, s, d, d, d, d, -e, 0]进行前缀和处理，能得到我们期望的结果。为了方便，我们将这个数组设为arr1。这时候，我们再想，是否有一个差分数组arr2，通过类似diff[l+1] += val diff[r+2] -= val的操作，经过前缀和处理，能得到arr1吗？

这样的数组，是存在的。我们说，差分数组实质上是前缀和数组的逆过程。那么，对于arr1的1号元素s，其实可以通过0 + x = s得到，这里的x是未知数，表示arr2第i号位置的数，这里的i为1。同理，对于arr2的2号元素d，可以通过s + x = d得到，求得x = d - s。同理，可以得到arr2其他位置上的元素。最后，求得arr2 = [0, s, d - s, 0, 0, 0, -e-d, e]。

也就是说，我们只需要求出diff差分数组，接着，按如下步骤操作：

diff[l+1] += s
diff[l+2] += (d - s)
diff[r+2] -= (e + d)
diff[r+3] += e

最后对该差分数组进行两次前缀和处理，就可以得到[0, s, s+d, s+2d, s+3d, e, 0, 0]

例题分析

3355. 零数组变换 I

给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。

对于每个查询 queries[i]：

在 nums 的下标范围 [li, ri] 内选择一个下标
子集。

将选中的每个下标对应的元素值减 1。

零数组是指所有元素都等于 0 的数组。

如果在按顺序处理所有查询后，可以将 nums 转换为零数组，则返回 true，否则返回 false。

解题

这题和1109. 航班预订统计类似，都需要我们在一个数组上的多个区间进行修改操作。因此，我们可以使用差分数组进行分析。

假设我们不考虑排除某一个下标做修改，对于每一个区间，我们对其每个元素都进行修改操作。我们申请一个长度为n+2，全为0的差分数组，对所有区间修改操作结束后，如果差分数组中，存在某个值小于nums[i]，说明修改操作不足以将这个数减为0。因为我们是可以在某一个操作中不选择修改这个元素的，所以如果这个数能变为0，那么差分数组应该满足diff[i] >= nums[i]。

由此，可以写出代码：

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> diff(n+2, 0);
        for (auto op : queries) {
            int l = op[0], r = op[1];
            diff[l+1]++;
            diff[r+2]--;
        }
        for (int i = 0; i < n; ++i) {
            diff[i+1] += diff[i];
            if (diff[i+1] < nums[i]) {
                return false;
            }
        }
        return true;
    }
};

时间复杂度分析

假设数组长度为n，执行的操作为k，显然，时间复杂度应该为O(n*k)

求第一个入环的点

发表于 2024-11-27 分类于链表本文字数： 1.6k 阅读时长 ≈ 3 分钟

基本思路

开始时快指针走两步，慢指针走一步
如果相遇，则找到第一个相遇的点
快指针回到头结点，慢指针原地不动
快慢指针各走一步，这时再相遇的点就是入环节点

链表类型例题

LCR 022. 环形链表 II

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

第一种方法，不考虑题目中限定的解决方案条件，可以使用hash_set记录遍历过的节点，如果再次遍历到该节点，说明成环且该节点就是入环的节点。

第二种方法，采用我们之前提到的思路，可以省去额外的空间，且空间复杂度为O(1)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next || !head->next->next) {
            return nullptr;
        }
        ListNode* slow = head->next;
        ListNode* fast = head->next->next;
        while (fast != slow) {
            if (!fast->next || !fast->next->next) {
                return nullptr;
            }
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

数组类型例题

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

如果我们根据数组的元素进行坐标跳转，会发现一个规律，最后这个跳转的过程会形成一个环，而入环的节点，就是这个重复的数。

因此，我们可以依照之前提到的流程，进行解答。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return 0;
        }
        int slow = nums[0];
        int fast = nums[nums[0]];
        // 找到第一个相遇的点
        while (fast != slow) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        // fast回到头结点，slow待在原地
        fast = 0;
        // 每次各跳一步，直到相遇，此时相遇的点就是入环的点
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
};

归并分治

发表于 2024-11-24 分类于递归本文字数： 1.7k 阅读时长 ≈ 3 分钟

思路

简要来说，归并分治的思路就是，在归并排序的基础上，统计答案。

具体而言，可以从以下步骤进行考虑：

答案是否可以从左区间、右区间和左跨右区间得到。
排序是否对寻找答案有利。

例题分析

翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

依题意，实际为找满足nums[左] > 2*nums[右]的个数。

考虑暴力方法，对于每个坐标，依次向右遍历，寻找是否满足nums[i] > 2*nums[j]的坐标，同时进行计数。显然，暴力解的时间复杂度是O(n^2)的。

尝试使用归并分治的思想进行求解，注意到，如果取中点mid，答案可以从左区间、右区间和左跨右区间得到。接下来，考虑第二点，排序是否对寻找答案有利？对于两个已经排好序的数组而言，可以分别看成左边元素的集合和右边元素的集合，对于单个集合中的元素而言，此时坐标顺序已不重要，因为在下游的递归中，我们已经得到了那部分的结果。此时，我们可以使用滑动窗口的思想，即一次遍历，寻找答案。设定两个指针，i和j，分别在左部分和右部分中迭代，满足条件nums[左] > 2*nums[右]时，j向右边遍历，直到越界。因为对于左部分，顺序是按从小到大排序的，即是说，*左部分[l, mid]的元素如果在右部分[mid+1, r]*有三个元素满足，对于左部分的下一个元素而言，它至少有三个元素满足。由此，我们可以用如下代码，统计答案。

int ans = 0;
for (int i = l, j = mid+1; i <= mid; ++i) {
    while (j <= r && 1LL * nums[i] > 1LL * nums[j] << 1) {
        j++;
    }
    ans += j - mid - 1;
}

这道题的整体代码则如下：

class Solution {
public:
    int help[50000] = {0};
    int merge(vector<int>& nums, int l, int mid, int r) {
        // 统计过程
        int ans = 0;
        for (int i = l, j = mid+1; i <= mid; ++i) {
            while (j <= r && 1LL * nums[i] > 1LL * nums[j] << 1) {
                j++;
            }
            ans += j - mid - 1;
        }
        // 归并排序过程
        int i = l, a = l, b = mid + 1;
        while (a <= mid && b <= r) {
            help[i++] = nums[a] <= nums[b] ? nums[a++] : nums[b++];
        }
        while (a <= mid) {
            help[i++] = nums[a++];
        }
        while (b <= r) {
            help[i++] = nums[b++];
        }
        for (int j = l; j <= r; ++j) {
            nums[j] = help[j];
        }
        return ans;
    }
    int mergeSort(vector<int>& nums, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + (r - l) / 2;
        return mergeSort(nums, l, mid) + mergeSort(nums, mid+1, r) + merge(nums, l, mid, r);
    }
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        return mergeSort(nums, 0, n-1);
    }
};

时间复杂度

一般情况下，归并分治的时间复杂度和归并排序一致，为O(n*log n)