滑窗问题实验LC2653（一次遍历维持窗口元素保持排序）

在只有一次遍历（即滑窗每向右移动一步只处理新增元素和删除旧元素）的前提下，要维持当前窗口内元素的全局“可排序”结构

问题背景：LeetCode 2653 - 滑动子数组的美丽值

题目要求在大小为 k 的滑动窗口中，找到第 x 小的整数。如果这个数是负数，则它就是该窗口的“美丽值”；否则，美丽值为 0。数组元素 nums[i] 的范围是 [-50, 50]。

下面是针对您提供的每种 C++ 实现的分析：

---

1. 平衡二叉搜索树 (std::multiset) - beauty_multiset

• 结构与原理：
  std::multiset 是 C++ STL 中的关联容器，底层通常由红黑树实现。它自动维护元素的有序性，并允许存储重复元素。
• 实现分析 (beauty_multiset):
  1. 初始化：空 multiset。
  2. 添加新元素 (win.insert(nums[i]))：O(log k)。
  3. 删除旧元素 (win.erase(win.find(nums[i - k])))：win.find() 是 O(log k)，win.erase(iterator) 也是 O(log k)（摊销）。这里使用 find 是为了确保当有重复元素时，只删除一个匹配的实例。
  4. 查询第 x 小元素：

     auto it = win.begin();
     advance(it, x - 1); // O(x) 操作
     int v = *it;
     

     win.begin() 得到指向最小元素的迭代器。std::advance(it, x - 1) 将迭代器向前移动 x-1 步，定位到第 x 小的元素。这个操作的复杂度是 O(x)，在最坏情况下（x 接近 k）是 O(k)。
• 时间复杂度：
  • 每个元素入窗和出窗各一次，每次 O(log k)。
  • 每次窗口滑动后查询第 x 小，需要 O(x)。
  • 总共 N 个元素，窗口滑动 N-k+1 次。
  • 总体复杂度：O(N * (log k + x))。由于 x <= k，可以认为是 O(N * (log k + k))，即 O(N * k)。
  • 注：如果使用支持 Order-Statistic Tree (如 GNU PBDS tree)，查询第 x 小可以是 O(log k)，总复杂度可降至 O(N log k)。
• 空间复杂度：O(k)，存储窗口内元素。
• 优点：代码简洁，逻辑清晰，直接利用了 multiset 的有序性。
• 缺点：查询第 x 小元素时 std::advance 效率不高，导致整体复杂度偏高。

---

2. 双堆 + 延迟删除 - beauty_two_heaps

• 结构与原理：
  通常用一个最大堆 small（存较小的一半元素）和一个最小堆 large（存较大的一半元素）来动态维护中位数。为了找到第 x 小的元素，这个结构需要调整：
  • small (最大堆) 应该存储窗口中最小的 x 个元素。
  • large (最小堆) 应该存储窗口中剩下的 k-x 个较大的元素。
  • 第 x 小的元素就是 small.top()。
  • 延迟删除通过一个哈希表 delayed 记录待删除元素的计数，当这些元素出现在堆顶时才真正移除。
• 实现分析 (beauty_two_heaps):
  • 平衡逻辑 (rebalance):

    if ((int)small.size() > (int)large.size() + 1) { /* ... */ }
    else if (small.size() < large.size()) { /* ... */ }
    

    这段平衡代码的目标是使 small 和 large 的大小尽量接近（small 最多比 large 大1），这是为中位数设计的。对于第 x 小元素，平衡逻辑应调整为：
    • 如果 small.size() > x，将 small.top() 移到 large。
    • 如果 small.size() < x 且 large 不空，将 large.top() 移到 small。
  • 插入新元素 (v):
    先尝试放入 small 或 large，然后调用 rebalance。
  • 删除滑出元素 (out):
    在 delayed 中标记，如果 out 可能影响堆顶，则调用 pruneSmall() 或 pruneLarge() 清理，然后 rebalance。
  • 查询第 x 小元素:

    int kth = small.top();
    

    这依赖于 small 堆正确维护了窗口中最小的 x 个元素，且其堆顶就是第 x 小的。以当前代码的 rebalance 逻辑，small.top() 并不总是第 x 小的元素，除非 x 恰好是 small 堆的目标大小（约 k/2）。
    例如，若 k=5, x=1，当前 rebalance 可能使 small 有3个元素，large 有2个，small.top() 并非第1小。
• 时间复杂度 (假设修正为 x-th smallest 的平衡逻辑)：
  • 插入、删除（含平衡、清理）：摊销 O(log k)。
  • 查询：O(1) (取 small.top()) + 可能的堆顶清理 O(log k)。
  • 总体复杂度：O(N log k)。
• 空间复杂度：O(k) (存储堆元素) + O(k) (最坏情况 delayed 哈希表大小)。
• 优点：如果正确为第 x 小元素调整平衡逻辑，查询快。
• 缺点：实现复杂，容易出错。当前代码的平衡逻辑是为中位数设计的，直接用于第 x 小元素会有问题，除非 x 约等于窗口大小的一半。需要修改 rebalance 和插入逻辑，确保 small 堆的大小严格维持在 x。

---

3. 有序数组 + 二分插入/删除 - beauty_ordered_array

• 结构与原理：
  维护一个固定大小 k 的 std::vector，并始终保持其有序。
• 实现分析 (beauty_ordered_array):
  1. 初始化：取前 k 个元素放入 window，然后排序 (O(k log k))。
  2. 查询第 x 小元素：window[x-1]，O(1)。
  3. 滑动窗口：
     • 删除 nums[i-k]：lower_bound 找到位置 (O(log k))，window.erase(iterator) 移动元素 (O(k)).
     • 插入 nums[i]：upper_bound 找到位置 (O(log k))，window.insert(iterator, value) 移动元素 (O(k)).
• 时间复杂度：
  • 初始化：O(k log k).
  • 每次滑动：删除 O(k) + 插入 O(k)。
  • 总体复杂度：O(k log k + (N-k) * k) = O(N * k)。
• 空间复杂度：O(k)，存储窗口内元素。
• 优点：实现相对简单，直接操作有序数组。对于 k 很小的情况，常数因子可能较低。
• 缺点：插入和删除操作中的元素移动导致 O(k) 的耗时，窗口大时性能较差。

---

4. 计数排序 / 桶排序 - beauty_counting

• 结构与原理：
  利用题目中元素值域 [-50, 50] 非常小的特点。使用一个计数数组 cnt 记录窗口内每个值出现的次数。由于数组下标不能为负，需要一个 OFFSET。
• 实现分析 (beauty_counting):
  1. OFFSET = 50，值 v 映射到 cnt 数组下标 v + OFFSET。cnt 数组大小为 101 (覆盖 -50 到 +50)。
  2. 添加新元素：cnt[nums[i] + OFFSET]++，O(1)。
  3. 删除旧元素：cnt[nums[i - k] + OFFSET]--，O(1)。
  4. 查询第 x 小元素:

     int csum = 0, beauty = 0;
     for (int idx = 0; idx <= 100; idx++) { // 遍历值域csum += cnt[idx];if (csum >= x) {int v = idx - OFFSET;beauty = v < 0 ? v : 0;break;}
     }
     

     从最小值 (-50) 开始遍历计数数组，累加元素出现次数 csum，直到 csum >= x。此时对应的 idx - OFFSET 就是第 x 小的元素。此操作复杂度为 O(ValueRange)。
• 时间复杂度：
  • 添加/删除：O(1)。
  • 查询：O(ValueRange)。在这里 ValueRange 是 101，是个常数。
  • 总体复杂度：O(N * ValueRange)，对于此题是 O(N * 101) \approx O(N)。
• 空间复杂度：O(ValueRange)，存储计数数组。
• 优点：利用了值域限制，实现了非常高效的更新和查询。对于此题是最佳方案。
• 缺点：仅适用于值域较小或可以有效离散化的情况。

---

5. Treap (随机平衡二叉搜索树) - beauty_treap

• 结构与原理：
  Treap 是一种随机化的平衡二叉搜索树，通过为每个节点赋予一个随机优先级，并同时满足 BST 性质（按键值）和堆性质（按优先级）来维持平衡。期望操作复杂度为 O(log k)。
• 实现分析 (beauty_treap):
  • Treap 节点：包含 key（值）、pri（随机优先级）、sz（子树大小）、l、r 指针。sz 对于快速查找第 x 小元素至关重要。
  • insert_treap 和 delete_treap：标准的 Treap 插入和删除操作，通过旋转维持平衡，期望 O(log k)。
  • 查询第 x 小元素:

    vector<int> tmp;
    inorder(root, tmp); // O(k) 中序遍历得到有序序列
    int v = tmp[x - 1]; // O(1)
    

    当前实现通过中序遍历将整个 Treap 元素存入 vector，然后取第 x-1 个。这使得查询操作为 O(k)。
  • 优化查询：利用节点中的 sz (子树大小) 属性，可以在 Treap 中直接查找第 x 小元素，时间复杂度为 O(log k)。

    // 伪代码 (find_kth)
    Treap* find_kth(Treap* t, int rank) {if (!t) return nullptr;int left_size = size(t->l);if (rank == left_size + 1) return t;if (rank <= left_size) return find_kth(t->l, rank);return find_kth(t->r, rank - (left_size + 1));
    }
    // ... 调用时:
    // Treap* node = find_kth(root, x);
    // int v = node->key;
    

• 时间复杂度 (当前实现)：
  • 插入/删除：期望 O(log k)。
  • 查询：O(k) (由于中序遍历)。
  • 总体复杂度：O(N * k)。
• 时间复杂度 (若查询优化为 O(log k))：
  • 总体复杂度：期望 O(N log k)。
• 空间复杂度：O(k)，存储 Treap 节点。
• 优点：一种通用的平衡树结构。如果实现 O(log k) 的第 x 小查询，性能很好。
• 缺点：实现复杂，常数因子可能较大。当前查询实现未利用 Treap 的优势。

---

主接口 getSubarrayBeauty 与选型建议

vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {// 推荐：由于 nums[i] ∈ [-50,50]，使用计数法最快return beauty_counting(nums, k, x);// ... 其他方法 ...
}

• 对于 LeetCode 2653 这道题:

  • 最佳选择：beauty_counting (计数排序)。因为元素值域 [-50, 50] 非常小且固定，计数排序的 O(N * ValueRange) 复杂度在此题中接近 O(N)，是最优的。
  • 次优选择 (通用情况)：
    • beauty_multiset：如果使用支持 O(log k) 查第 x 小的平衡树 (如 PBDS tree)，则为 O(N log k)。标准 multiset 是 O(N * (log k + x))。
    • beauty_two_heaps：如果正确实现针对第 x 小元素的平衡逻辑（确保 small 堆大小为 x），则为 O(N log k)。
    • beauty_treap：如果实现 O(log k) 查第 x 小，则为 O(N log k)。
  • 较慢选择：
    • beauty_ordered_array：O(N * k)，k 较大时会超时。

• 代码中的 beauty_two_heaps 的问题: 如前所述，它的平衡逻辑是为中位数设计的。若要正确用于第 x 小，rebalance 函数和可能的元素分配逻辑（插入时元素进 small 还是 large）需要调整，目标是始终让 small (最大堆) 包含窗口中最小的 x 个元素。

实验 lc2653

2653. 滑动子数组的美丽值

#include <bits/stdc++.h>using namespace std;class Solution {public:// ---------- 1. 平衡树 (multiset) ----------vector<int> beauty_multiset(vector<int>& nums, int k, int x) {multiset<int> win;vector<int> ans;for (int i = 0; i < (int)nums.size(); i++) {win.insert(nums[i]);if (i >= k)win.erase(win.find(nums[i - k]));if (i >= k - 1) {// 取第 x 小auto it = win.begin();advance(it, x - 1);int v = *it;ans.push_back(v < 0 ? v : 0);}}return ans;}// ---------- 2. 双堆 + 延迟删除 ----------vector<int> beauty_two_heaps(vector<int>& nums, int k, int x) {priority_queue<int> small;                            // max-heappriority_queue<int, vector<int>, greater<int>> large; // min-heapunordered_map<int, int> delayed;// 对 small 队列中被延迟删除的元素进行真正删除auto pruneSmall = [&]() {while (!small.empty()) {int v = small.top();if (delayed.count(v)) {if (--delayed[v] == 0)delayed.erase(v);small.pop();} elsebreak;}};// 对 large 队列中被延迟删除的元素进行真正删除auto pruneLarge = [&]() {while (!large.empty()) {int v = large.top();if (delayed.count(v)) {if (--delayed[v] == 0)delayed.erase(v);large.pop();} elsebreak;}};// 保持两个堆的大小平衡：|small| == |large| 或者 |small| == |large|+1auto rebalance = [&]() {if ((int)small.size() > (int)large.size() + 1) {large.push(small.top());small.pop();pruneSmall();} else if (small.size() < large.size()) {small.push(large.top());large.pop();pruneLarge();}};vector<int> ans;for (int i = 0; i < (int)nums.size(); i++) {int v = nums[i];if (small.empty() || v <= small.top())small.push(v);elselarge.push(v);rebalance();if (i >= k) {int out = nums[i - k];delayed[out]++;if (out <= small.top())pruneSmall();elsepruneLarge();rebalance();}if (i >= k - 1) {int kth =small.top(); // 此处 small.top() 就是窗口内第 x 小（若 x=1）ans.push_back(kth < 0 ? kth : 0);}}return ans;}// ---------- 3. 有序数组 + 二分插入/删除 ----------vector<int> beauty_ordered_array(vector<int>& nums, int k, int x) {vector<int> window(nums.begin(), nums.begin() + k), ans;sort(window.begin(), window.end());for (int i = k;; i++) {int v = window[x - 1];ans.push_back(v < 0 ? v : 0);if (i == (int)nums.size())break;// 删除 nums[i-k]，插入 nums[i]auto it = lower_bound(window.begin(), window.end(), nums[i - k]);window.erase(it);window.insert(upper_bound(window.begin(), window.end(), nums[i]),nums[i]);}return ans;}// ---------- 4. 计数排序 / 桶排序 (值域 [-50,50]) ----------vector<int> beauty_counting(vector<int>& nums, int k, int x) {const int OFFSET = 50;vector<int> cnt(101, 0), ans;for (int i = 0; i < (int)nums.size(); i++) {cnt[nums[i] + OFFSET]++;if (i >= k)cnt[nums[i - k] + OFFSET]--;if (i >= k - 1) {int csum = 0, beauty = 0;for (int idx = 0; idx <= 100; idx++) {csum += cnt[idx];if (csum >= x) {int v = idx - OFFSET;beauty = v < 0 ? v : 0;break;}}ans.push_back(beauty);}}return ans;}// ---------- 5. Treap（随机平衡二叉搜索树） ----------struct Treap {int key, pri, sz;Treap *l, *r;Treap(int _k) : key(_k), pri(rand()), sz(1), l(nullptr), r(nullptr) {}};int size(Treap* t) { return t ? t->sz : 0; }void upd(Treap* t) {if (t)t->sz = 1 + size(t->l) + size(t->r);}Treap* rotate_right(Treap* y) {Treap* x = y->l;y->l = x->r;x->r = y;upd(y);upd(x);return x;}Treap* rotate_left(Treap* x) {Treap* y = x->r;x->r = y->l;y->l = x;upd(x);upd(y);return y;}Treap* insert_treap(Treap* t, int k) {if (!t)return new Treap(k);if (k < t->key) {t->l = insert_treap(t->l, k);if (t->l->pri < t->pri)t = rotate_right(t);} else {t->r = insert_treap(t->r, k);if (t->r->pri < t->pri)t = rotate_left(t);}upd(t);return t;}Treap* delete_treap(Treap* t, int k) {if (!t)return nullptr;if (t->key == k) {if (!t->l || !t->r) {Treap* c = t->l ? t->l : t->r;delete t;return c;}if (t->l->pri < t->r->pri) {t = rotate_right(t);t->r = delete_treap(t->r, k);} else {t = rotate_left(t);t->l = delete_treap(t->l, k);}} else if (k < t->key) {t->l = delete_treap(t->l, k);} else {t->r = delete_treap(t->r, k);}upd(t);return t;}void inorder(Treap* t, vector<int>& out) {if (!t)return;inorder(t->l, out);out.push_back(t->key);inorder(t->r, out);}vector<int> beauty_treap(vector<int>& nums, int k, int x) {Treap* root = nullptr;vector<int> ans;for (int i = 0; i < (int)nums.size(); i++) {root = insert_treap(root, nums[i]);if (i >= k)root = delete_treap(root, nums[i - k]);if (i >= k - 1) {vector<int> tmp;inorder(root, tmp);int v = tmp[x - 1];ans.push_back(v < 0 ? v : 0);}}return ans;}// 主接口，调用你想用的任意一种：vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {// 推荐：由于 nums[i] ∈ [-50,50]，使用计数法最快return beauty_counting(nums, k, x);// 其他几种可切换为：// return beauty_multiset(nums, k, x);// return beauty_two_heaps(nums, k, x);// return beauty_ordered_array(nums, k, x);// return beauty_treap(nums, k, x);}};