解压缩：从CCF-CSP真题看数据结构的妙用

在解决《202305-3 解压缩》这题时，我们首先需要理解题目的要求。题目要求我们从给定的字符串中提取出每个元素对应的下标，并且下标必须是连续递增的。这是一个典型的滑动窗口问题，我们可以使用双端队列来解决。
首先，我们将原字符串的每个元素存入一个双端队列，这样元素的相对顺序就被保存了下来。然后，我们使用一个变量来记录当前队列的尾部元素的下标，即窗口的右边界。每次我们移动左边界，都将窗口内的元素出队，并将新的元素入队。同时，我们更新尾部元素的下标。
具体实现时，我们可以使用Python或C++。以下是这两种语言的满分代码实现：
Python版：

from collections import deque
def decode(s: str) -> List[int]:
n = len(s)
dq = deque()
res = []
for i in range(n):
dq.append(i)
while dq[0] <= i - 2:
dq.popleft()
res.append(i - dq[0])
return res

C++版：

#include <queue>
#include <vector>
using namespace std;
vector<int> decode(string s) {
int n = s.size();
priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆，保存下标
vector<int> res;
for (int i = 0; i < n; ++i) {
pq.push(i);
while (pq.top() <= i - 2) { // 当队列头部元素的下标小于等于当前位置的前两个位置时，出队
pq.pop();
}
res.push_back(i - pq.top()); // 当前位置与队列头部元素的下标的差即为当前位置对应元素的索引
}
return res;
}

在这两个实现中，我们使用了双端队列来保存元素的相对顺序，并使用滑动窗口来处理连续递增的下标要求。在Python实现中，我们使用了列表来表示双端队列，而在C++实现中，我们使用了小顶堆来保持下标的相对顺序。这两种实现方式都非常高效，时间复杂度均为O(n)，其中n为字符串的长度。